Дизайн NFA с изменением алфавита и языка

Я столкнулся с этим упражнением, думал об этом несколько часов и ни к чему не пришел.

наш алфавит {1...n}, а наш язык Ln содержит все слова до Σ*, так что каждое слово в языке не содержит хотя бы одной буквы из алфавита.

  • например: если n=5, слово w={111223432} есть в языке, потому что в этом слове отсутствует '5'. слова w={1352224} нет в языке, потому что все буквы 1...n есть в этом слове.

Мне нужно разработать NFA для этого языка с n+1 состояниями.

Опять же, я попробовал несколько вещей и не совсем понял.


automaton nfa
person user76508    schedule 18.11.2014    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Для простоты сделаем это для алфавита {a, b, c}. Представьте, что у вас есть строка на вашем языке. Это означает, что отсутствует a, или отсутствует b, или отсутствует c (включая или). Если бы мы знали, какой символ отсутствует, было бы очень легко проверить, не было ли в строке копии этого символа, используя NFA с одним состоянием, состоящим из принимающего состояния, которое переходит обратно в себя для всего, кроме этого символа.

Поскольку в алфавите только конечное число символов, мы можем построить три NFA с одним состоянием, каждое из которых предназначено для проверки того, отсутствует ли в строке определенный символ.

Чтобы построить машину в целом, пусть начальное состояние NFA недетерминистически угадывает, какой символ отсутствует, добавляя -transitions из начального состояния к каждому из отдельных NFA с одним состоянием, которые мы создали ранее. Теперь у вас есть NFA с четырьмя состояниями для этого языка. (Вы можете увидеть его изображение здесь.) Надеюсь, не слишком сложно понять, как обобщить это до больших размеров алфавита!

person templatetypedef    schedule 30.08.2016