Как мне найти язык для грамматики без контекста?

Question

У меня проблемы с определением языка по заданной контекстно-свободной грамматике.Мне дали подсказку, что в языке есть две части, но я не могу понять.

G= ({S,A,B,C,D,E,Z},(0,1),R,S),

S→E|Z
E→A|C 
A→01B|0A|e
B→1B|10A 
C→10D|1C|e
D→01C|0D 
Z→0Z1|e

Кстати, пустая строка.Я понял, что если это Z, то число 0 и 1 равны, но не могу понять, что, если оно переходит к E

Answer 1

Вроде не по теме, но вы можете довольно легко разбить грамматику на подпрограммы, которые вы можете анализировать самостоятельно.

Во-первых, правило E появляется только в одном месте в RHS, так что вы можететривиально подставьте его и избавьтесь от него, сделав правило S S→A|C|Z.Каждый из этих нетерминалов приводит к независимому подъязыку (язык A, состоящий только из правил для A и B, язык C с просто C и D и язык Z с просто Z.язык G является просто объединением этих трех подъязыков.

Язык А тривиально регулярен (из-за того, что все нетерминалы находятся в конце RHS правил) и может быть тривиально преобразован в состояние 2E-NFA, который сводится к регулярному выражению (0 | 011 * 10) *

Язык C аналогично сводится к регулярному выражению (1 | 100 * 01) *

Язык Z является единственным нерегулярный подраздел и является языком {0 ⁱ 1 ⁱ | i ≥ 0}

Объединение этих трех является языком G и на самом деле не имеет каких-либохороший способ описать это, кроме грамматики.