язык Задание для данной грамматики

Question

задачи DFA: Напишите полную грамматику для L, в том числе четыре раза и правил производства

L ={x: ∃y ∈ {a, b}* : x = ay} 

Ответ:

G={{S, A}, {a, b}, S, P} 
P: S => aA 
    A => aA | bA | λ 

Мой вопрос:

1. Почему существует λ для A, но нет λ для S?
2. Из определения языка, это любая строка, которая начинается с a и содержит только a и b, но почему в ответе A => bA. Разве это не означает, что строка начинается с b, если это A => bA?

Спасибо большое

Answer 1

1. Почему есть λ для A, но нет λ для S?

λ nul может быть получен из A, чтобы преобразовать сентиментальный из в предложение. Кроме того, в соответствии с инструкцией по языку префикс подстрокой y ∈ {a, b}* может быть nul (пустая строка), например. "a" - строка, относящаяся к языку. Если y содержит любой символ, тогда длина языка будет более одного.

S не выводит λ nul, потому что пустой (или сказать nul string) не на языке. Самая маленькая строка на языке одна "a".

2. Из определения языка, это любая строка, которая начинается с a и содержит только a «S и b» с, но почему в ответе A => bA. Разве это не означает, что строка начинается с b, если это A => bA?

Примечание только строки те могут производные от начальной переменной S включены в языке грамматики. Вы не можете начать вывод из A (это не начальная переменная). И если вы начинаете деривацию с S, ваша строка всегда будет начинаться с символа a.

Предлагаю вам прочитать: "Why the need for terminals? Is my solution sufficient enough?" Где я писал об основном определении формальной грамматики.