跳转至

给出语言写文法的方法

image.png - 一些解题思路： - 将拆分成几个部分 - 按照内外层逐个构造

拆分

\(L_1\sim L_3\)的解题思路一致，将语言拆分成两个部分：image.png 然后对每个单元进行构造即可 image.png

分层

对于\(L_4\)可以将其分为内外层次，先构造外层，然后通过产生式进入内层继续构造image.png - 先构造外层的\(1^n0^n\) - 利用产生式进入内层继续构造 - 对于内层的逻辑一致 image.png

对于常见单元的产生式

  • \(a^n b^n, n\ge1\)：\(A\rightarrow aAb|ab\)
  • \(a^i b^i, i\ge0\)：\(A\rightarrow aAb|\varepsilon\)