将文法正式表述为 4 元组
Stating a grammar formally as a 4 tuple
拿到了这个面试q，我知道很容易，但我好像做不到。
State the following grammar formally as a 4-tuple. (Assume the terminal alphabet is the set of lowercase letters the appear in productions, the nonterminal alphabet is the set of uppercase letters that appear in productions and the start symbol is S.)
S -> abS|X
X -> baX|epsilon
文法 G 被定义为四元组 (N, S, E, P)，其中：
- N 是一组有限的非终结符号
- N的元素S为起始符号
- E 是一组有限的终结符号
- N 和 E 不相交
- P 是一组产生式，或超过 (N + E)* x (N + E)*
的有序对
如果在 P 中存在 w[1]、w[2]、...、w[n] 个产生式序列，则文法 G 中存在字符串 w 的推导，使得：
- w[1] = S
- 对于每个 1 <= i < n：w[i] = xyz，w[i+1] = xy'z 并且 (y, y') 是 P
中的产生式
- w[n] = w是一串终结符。
在G中有推导的所有字符串w的集合称为G的语言，L(G)。
现在，对于你的语法：
- 非终结符号：S、X
- 起始符号：S
- 终端符号：a、b
- 产生式：(S, abS)、(S, X)、(X, baX)、(X, epsilon)
拿到了这个面试q，我知道很容易，但我好像做不到。
State the following grammar formally as a 4-tuple. (Assume the terminal alphabet is the set of lowercase letters the appear in productions, the nonterminal alphabet is the set of uppercase letters that appear in productions and the start symbol is S.) S -> abS|X
X -> baX|epsilon
文法 G 被定义为四元组 (N, S, E, P)，其中：
- N 是一组有限的非终结符号
- N的元素S为起始符号
- E 是一组有限的终结符号
- N 和 E 不相交
- P 是一组产生式，或超过 (N + E)* x (N + E)* 的有序对
如果在 P 中存在 w[1]、w[2]、...、w[n] 个产生式序列，则文法 G 中存在字符串 w 的推导，使得：
- w[1] = S
- 对于每个 1 <= i < n：w[i] = xyz，w[i+1] = xy'z 并且 (y, y') 是 P 中的产生式
- w[n] = w是一串终结符。
在G中有推导的所有字符串w的集合称为G的语言，L(G)。
现在，对于你的语法：
- 非终结符号：S、X
- 起始符号：S
- 终端符号：a、b
- 产生式：(S, abS)、(S, X)、(X, baX)、(X, epsilon)