这种上下文无关语言是否规则？
Is this context free language regular?
如果我有一种语言 {0,1} 由以下上下文无关文法定义，起始变量为 S，它是一种常规语言吗？
S→TS, S→1T, S→1S
T→TT, T→0T1, T→1T0 T→ε
这种语言是正规的吗？
在我看来，这种语言不可能是正则的，因为它基本上是终端和变量的任意组合。而常规语言需要是右线性或左线性。我是对的，还是我的想法不正确？是否有任何人推荐用于确定上下文无关语法是否正常的特定过程？
与语法相关的语言不规则。 post 的其余部分与此陈述的证明有关。
首先，请注意 L(T) = {w over {0,1} | w contains equal number of 0s and 1s}.
你可以很容易地证明这一点。
证明思路。 (==>)假设w在L(T)。那么显然有相同数量的0和1。
(<==) 假设 w 包含相等数量的 0 和 1。我们通过归纳证明 w 可从 T 导出。如果 |w|<=2，那么它显然可以从 T 导出。假设，对于归纳假设，所有长度为 k（偶数长度）且 0 和 1 的数量相等的字符串都可以从 T 导出。令 w 的长度为 k+2。如果 w 的第一个和最后一个字符匹配（均为 0 或均为 1），则应用产生式 T -> TT；第一部分和最后一部分都可以通过归纳假设从 T 导出；在这里，我们使用明显的 属性 如果 w[0]=w[|w|-1] 那么存在一个索引 i 这样 w[0..i] 和 w[i+1..|w|-1] 都在 L(T)，并且都可以通过归纳假设从 T 推导出来。否则，如果 w 的第一个和最后一个字符不匹配，请使用 T -> 0T1 或 T -> 1T0；结果字符串的长度为 k 并且可以根据归纳假设从 T 导出。 QED.
现在，文法的语言就是S可以生成的字符串集合。请注意，S 生成形式为 (T+1)*1T 的字符串（包含终结符和变量）。换句话说，对于语法可导出的任何终端字符串 w，它必须是 S =>* α =>* w 的情况，其中 α 在 (T+1)*1T.
中
现在应该很明显，可以由S生成的所有可能终端的集合由正则表达式(L(T)* + 1)*1L(T)*表征。 （您可以通过检查可以从 (T+1)*1T 生成的一组终端字符串来得出这一点。）
您可以简化 L(S) 的表达式：(L(T)+1)*1L(T)=(L(T)+1)* 因为 1L(T) 的语言是 (L(T)+1)^2 的语言的子集。因此 L(S) = (L(T)+1)*，该语言由包含至少与 0 一样多的 1 的二进制字符串组成。
这种语言不正规。您可以使用 pumping lemma.
来证明这一点
证明。为了矛盾起见，假设 L(S) 是正则的。然后，根据抽水引理，有 n>0 这样 L(S) 中的每个 w 长度至少 n 可以分解成 w=xyz 这样：
|xy| <= n,y non-empty,- 对于
L(S) 中的所有 k >= 0、xy^ky。
设 w=0^n1^n 为来自 L(S) 的长度为 m=2n 的字符串。 （引理讨论了来自 L(S) 的 all 足够长的字符串，因此我们可以选择任何我们喜欢的字符串并且仍然具有这些属性。）让 w=xyz 成为一个分区由引理存在。显然，由于 m=2n 和 |xy|<=n，y 仅由 0 组成（并且至少有一个 0，因为 y 不为空） .
很明显，xy^2z 中的 0 多于 1，因此不在 L(S) 中。这与泵引理相矛盾。因此，L(S) 不是正则的。 QED.
如果我有一种语言 {0,1} 由以下上下文无关文法定义，起始变量为 S，它是一种常规语言吗？ S→TS, S→1T, S→1S T→TT, T→0T1, T→1T0 T→ε
这种语言是正规的吗？
在我看来，这种语言不可能是正则的，因为它基本上是终端和变量的任意组合。而常规语言需要是右线性或左线性。我是对的，还是我的想法不正确？是否有任何人推荐用于确定上下文无关语法是否正常的特定过程？
与语法相关的语言不规则。 post 的其余部分与此陈述的证明有关。
首先，请注意 L(T) = {w over {0,1} | w contains equal number of 0s and 1s}.
你可以很容易地证明这一点。
证明思路。 (==>)假设w在L(T)。那么显然有相同数量的0和1。
(<==) 假设 w 包含相等数量的 0 和 1。我们通过归纳证明 w 可从 T 导出。如果 |w|<=2，那么它显然可以从 T 导出。假设，对于归纳假设，所有长度为 k（偶数长度）且 0 和 1 的数量相等的字符串都可以从 T 导出。令 w 的长度为 k+2。如果 w 的第一个和最后一个字符匹配（均为 0 或均为 1），则应用产生式 T -> TT；第一部分和最后一部分都可以通过归纳假设从 T 导出；在这里，我们使用明显的 属性 如果 w[0]=w[|w|-1] 那么存在一个索引 i 这样 w[0..i] 和 w[i+1..|w|-1] 都在 L(T)，并且都可以通过归纳假设从 T 推导出来。否则，如果 w 的第一个和最后一个字符不匹配，请使用 T -> 0T1 或 T -> 1T0；结果字符串的长度为 k 并且可以根据归纳假设从 T 导出。 QED.
现在，文法的语言就是S可以生成的字符串集合。请注意，S 生成形式为 (T+1)*1T 的字符串（包含终结符和变量）。换句话说，对于语法可导出的任何终端字符串 w，它必须是 S =>* α =>* w 的情况，其中 α 在 (T+1)*1T.
现在应该很明显，可以由S生成的所有可能终端的集合由正则表达式(L(T)* + 1)*1L(T)*表征。 （您可以通过检查可以从 (T+1)*1T 生成的一组终端字符串来得出这一点。）
您可以简化 L(S) 的表达式：(L(T)+1)*1L(T)=(L(T)+1)* 因为 1L(T) 的语言是 (L(T)+1)^2 的语言的子集。因此 L(S) = (L(T)+1)*，该语言由包含至少与 0 一样多的 1 的二进制字符串组成。
这种语言不正规。您可以使用 pumping lemma.
来证明这一点证明。为了矛盾起见，假设 L(S) 是正则的。然后，根据抽水引理，有 n>0 这样 L(S) 中的每个 w 长度至少 n 可以分解成 w=xyz 这样：
|xy| <= n,ynon-empty,- 对于
L(S)中的所有k >= 0、xy^ky。
设 w=0^n1^n 为来自 L(S) 的长度为 m=2n 的字符串。 （引理讨论了来自 L(S) 的 all 足够长的字符串，因此我们可以选择任何我们喜欢的字符串并且仍然具有这些属性。）让 w=xyz 成为一个分区由引理存在。显然，由于 m=2n 和 |xy|<=n，y 仅由 0 组成（并且至少有一个 0，因为 y 不为空） .
很明显，xy^2z 中的 0 多于 1，因此不在 L(S) 中。这与泵引理相矛盾。因此，L(S) 不是正则的。 QED.