grammar - 为给定语法指定语言

Question

DFA问题：为L写一个完整的文法，包括四元组和产生式规则

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

回答：

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

我的问题是：

1. 为什么有λfor A，却没有λfor S？
2. 从语言定义来看，它是任何以 an 开头a且仅包含a's 和b's 的字符串，但为什么在 answer 中A => bA。这是否意味着字符串以bif开头A => bA？

太感谢了

Answer 1

1.为什么有λfor A，却没有λfor S？

λnul 可以派生自A将感性的 from 转换为句子。另外根据语言声明前缀子字符串y ∈ {a, b}* 可以是nul（空字符串），例如"a"是属于该语言的字符串。如果y包含任何符号，则语言的长度将超过一。

S不派生λnul 因为空（或说 nul 字符串）不在语言中。语言中最小的字符串是 single "a"。

2.从语言定义来看，它是任何以 an 开头a且仅包含a's 和b's 的字符串，但为什么在 answer 中A => bA。这是否意味着字符串以bif开头A => bA？

请注意，只有 那些可以从 start 变量派生的字符串S才包含在语法语言中。你不能从A（那不是开始变量）开始推导。如果您从S字符串开始派生，则始终以a符号开头。

我建议您阅读：“为什么需要终端？我的解决方案是否足够？” 我在哪里写过形式语法的基本定义。