Formal Context Free Grammar Von Freier Kontext Sprache

Question

Wie kann eine formale kontextfreie Grammatik für die folgende Sprache generiert werden:

{ai bjck | i != j or j != k}

Ich habe folgende Produktionen, aber kann es nicht verstehen:

 S->AX | YC      unequal b’s c’s or a’s b’s 

    A-> aA | e      0 or more A’s 

    C -> cC |e      0 or more c’s 

    B -> bB | e     0 or more B’s 

    X -> bXc | bB | cC    equal b’s, c’s then 1+ b’s, 
            1+C’s (i.e. unequal b’s and c’s) 

    Y -> aYb | bB | aA    unequal a’s b’s 

Kann mir jemand helfen, dieses Problem zu verstehen und zu lösen?

Answer 1

Die Sprache L = {ai bj ck | i != j or j != k} kann einfach als L = L1 U L2 geschrieben werden, so dass L1 = {ai bj ck | i != j } und L1 = {ai bj ck | j != k }.

In L gibt es keine Einschränkung für Symbol c einzige Bedingung ist, numberOf(a) sollte nicht gleich zu numberOf(b). Entweder numberof(a)>numberOf(b)odernumberof(a)<. numberOf(b). So Grammatik für diese Sprache sollte sein:

L1 => EX    // L1 is start variable 
E => aEb | A | B 
X => C |^
A => aA | a 
B => bB | b 
C => cC | c 

In über Grammatik E mit können wir die gleiche Anzahl von a erzeugen und b im Muster der anEbn, dann diesen sentimental konvertieren aus in Satzform entweder E zu ersetzt durch B oder A, die verursacht eine Zeichenfolge in der Form, so dass ai bj mit i != j, mit Variable X eine beliebige Anzahl von c kann an das Muster ai bj suffixiert werden.

diese Grammatik zu verstehen lesen: Tips for creating Context free grammar und Why the need for terminals? Is my solution sufficient enough?

Ähnliches gilt für L dort a einzige Bedingung keine Beschränkung auf das Symbol ist, numberOf(b) sollte nicht gleich zu numberOf(c) sein. Entweder numberof(b)>numberOf(c)odernumberof(b)<. numberOf(c). So Grammatik für diese Sprache sein sollte:

L2 => YF    // L2 is start variable 
F => bFc | B | C 
Y => A |^
A => aA | a 
B => bB | b 
C => cC | c 

Nun sind beide dieser Grammatik ein mit einer neuen Start variable Einführung S und zwei neue Produktionsregeln S => L1 | L2 wir bekommt Grammatik für die Sprache L = {ai bj ck | i != j or j != k}.