从语言生成上下文无关语法
Generating context-free grammar from language
我需要为每个示例提供上下文无关语法:
L1 = {a^hb^ka^mb^n : h + k = m + n}
L2 = {a^ib^ja^k : (i = j and k >= 0) or (i >= 0 and j > k)}
我做了很多简单的例子,提高了我从语法生成 CFG 的技能。我通常从解决最简单的情况开始,然后从那里开始构建。但是,我对从哪里开始找到这些问题的解决方案感到困惑。
对于第一个,想象从外向内剥离符号。我们开始剥离 a 和 b 对:
S -> aSb
如果我们先剥离所有的a,我们需要去到一个新的状态;否则,如果我们先剥离所有的b,我们需要进入一个新的状态;否则,如果我们同时剥离两者,我们可以切换到剥离反向对:
S -> aSb
S -> aXa | bYb
S -> bZa
如果我们最终做 S -> aXa,我们需要用尽左边的 a 才能接受;否则,我们可以从两端继续剥离a:
S -> aSb | aXa | bYb | bZa
X -> aXa | bZa
同样适用于 Y:
S -> aSb | aXa | bYb | bZa
X -> aXa | bZa
Y -> bYb | bZa
现在对于 Z,我们只需要确保我们以空字符串结束:
S -> aSb | aXa | bYb | bZa
X -> aXa | bZa
Y -> bYb | bZa
Z -> bZa | e
如何证明这是正确的?首先,争辩说这只产生语言中的字符串。这里的一个证明想法是注意最后一个产生式是 Z -> e 并且到那时我们总是在它的两边添加相同数量的符号;同样,在左边,我们只能在 a 之后添加 b,而在右边,我们只能在 b 之前添加 a。然后,争辩说这会产生该语言中的所有字符串。这里的一个证明思路是描述一般情况下如何推导a^h b^k a^m b^n。分别考虑 h < n、h = n 和 h > n,在每种情况下分别考虑 k < m、k = m 和 k > m。
对于第二个,您的第一步应该是将其拆分为两种语言并消除分离:
L2 = A union B
A = {a^ib^ja^k : (i = j and k >= 0)}
B = {a^ib^ja^k : (i >= 0 and j > k)}
现在,找到 A 的语法:
A -> Aa | A'
A' -> aA'b | e
接下来,为 B 找到语法:
B -> aB | B'
B' -> bB'a | b
然后,写出 S 将 S 连接到 A 或 B 的语法:
S -> A | B
A -> Aa | A'
A' -> aA'b | e
B -> aB | B'
B' -> bB'a | b
证明留作练习。
我需要为每个示例提供上下文无关语法:
L1 = {a^hb^ka^mb^n : h + k = m + n}
L2 = {a^ib^ja^k : (i = j and k >= 0) or (i >= 0 and j > k)}
我做了很多简单的例子,提高了我从语法生成 CFG 的技能。我通常从解决最简单的情况开始,然后从那里开始构建。但是,我对从哪里开始找到这些问题的解决方案感到困惑。
对于第一个,想象从外向内剥离符号。我们开始剥离 a 和 b 对:
S -> aSb
如果我们先剥离所有的a,我们需要去到一个新的状态;否则,如果我们先剥离所有的b,我们需要进入一个新的状态;否则,如果我们同时剥离两者,我们可以切换到剥离反向对:
S -> aSb
S -> aXa | bYb
S -> bZa
如果我们最终做 S -> aXa,我们需要用尽左边的 a 才能接受;否则,我们可以从两端继续剥离a:
S -> aSb | aXa | bYb | bZa
X -> aXa | bZa
同样适用于 Y:
S -> aSb | aXa | bYb | bZa
X -> aXa | bZa
Y -> bYb | bZa
现在对于 Z,我们只需要确保我们以空字符串结束:
S -> aSb | aXa | bYb | bZa
X -> aXa | bZa
Y -> bYb | bZa
Z -> bZa | e
如何证明这是正确的?首先,争辩说这只产生语言中的字符串。这里的一个证明想法是注意最后一个产生式是 Z -> e 并且到那时我们总是在它的两边添加相同数量的符号;同样,在左边,我们只能在 a 之后添加 b,而在右边,我们只能在 b 之前添加 a。然后,争辩说这会产生该语言中的所有字符串。这里的一个证明思路是描述一般情况下如何推导a^h b^k a^m b^n。分别考虑 h < n、h = n 和 h > n,在每种情况下分别考虑 k < m、k = m 和 k > m。
对于第二个,您的第一步应该是将其拆分为两种语言并消除分离:
L2 = A union B
A = {a^ib^ja^k : (i = j and k >= 0)}
B = {a^ib^ja^k : (i >= 0 and j > k)}
现在,找到 A 的语法:
A -> Aa | A'
A' -> aA'b | e
接下来,为 B 找到语法:
B -> aB | B'
B' -> bB'a | b
然后,写出 S 将 S 连接到 A 或 B 的语法:
S -> A | B
A -> Aa | A'
A' -> aA'b | e
B -> aB | B'
B' -> bB'a | b
证明留作练习。