Я только начал изучать Теорию вычислений в этом семестре и немного смущен фразой «DFA для языка». Если ему предлагается построить DFA для некоторого набора двоичных строк L, значит ли это найти DFA M с L (M) = L или просто $ L (M) \ supset L $?Определение «DFA для языка»
Большинство курсов для компилятора/теории, как правило, имеют разные стили, связанные с обучением определениям детерминированных конечных автоматов и формальных языков, но я постараюсь сделать это описание максимально агностиком ,
Фраза «DFA для языка» свободно означает: DFA, который принимает каждый word на этом языке и отклоняет каждый word не на языке. То, как меня учили DFA, - иметь конечные/принимающие состояния и регулярные состояния, которые устраняют необходимость в неявном состоянии ошибки. Это означает, что DFA принимает слово, если состояние, в котором оно находится в конце ввода, равно accepting, и оно отвергает слово, если состояние не accepting.
Ex:
Давайте определим L как язык, который содержит четное число 1s. Это будут двоичные строки, поэтому символы равны 0 и 1. 00, 110,
, 111
1111 и т. Д. Являются примерами слов на этом языке. Обратите внимание, что пустая строка находится на этом языке.
Мы можем иметь два состояния в нашем DFA. Начальное состояние, назовем его even 1s, также принимающим состоянием, потому что 0 четных. Другое состояние: odd 1s, это не принимается.
Что касается переходов, когда even 1s получает 1, то он переходит на odd 1s. И когда odd 1s получает 1, он переходит на even 1s. Теперь число 0s не имеет значения, поэтому в любом состоянии оно переходит к самому себе.
Извиняюсь за двойной стрелкой, это website является большим, но я не мог понять, как отделить переходы между even 1s и odd 1s
Напишите свой вопрос точным способом. здесь DFA для языка означает, что вам нужно построить машину только для определенного языка, а не подмножество или надмножество. построить DFA maachine, для которого L (M) = L.