Задача DFA: напишите полную грамматику для L, включая четверку и правила производства.
L ={x: ∃y ∈ {a, b}* : x = ay}
Отвечать:
G={{S, A}, {a, b}, S, P}
P: S => aA
A => aA | bA | λ
Мой вопрос:
A есть λ, а для S нет λ?a и содержит только a и b, но почему в ответе A => bA. Не означает ли это, что строка начинается с b, если она A => bA?Большое спасибо
1.Почему дляAестьλ, а дляSнетλ?
λ nul может быть получено из A для преобразования сентиментального from в предложение. Кроме того, в соответствии с префиксом оператора языка подстрока y ∈ {a, b}* может быть нулевой (пустая строка), например. "a" — это строка, принадлежащая языку. Если y содержит любой символ, то длина языка будет больше единицы.
S не выводит λ nul, потому что пустой (или, скажем, нулевая строка) не является языком. Самая маленькая строка в языке — одиночная "a".
2.Из определения языка это любая строка, начинающаяся сaи содержащая толькоaиb, но почему в ответеA => bA. Не означает ли это, что строка начинается сb, если онаA => bA?
Обратите внимание, что только строки, которые могут быть получены из начальной переменной S, включены в язык грамматики. Вы не можете начать вывод из A (это не начальная переменная). И если вы начнете производное от S, ваша строка всегда будет начинаться с символа a.
Я предлагаю вам прочитать: "Почему нужны ли терминалы? Достаточно ли моего решения?" Где я написал об основном определении формальной грамматики.
