contesto formale libero Grammar Da Contesto Gratis Lingua

Question

Come può una grammatica libera dal contesto formale essere generato per la seguente lingua:

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

Ho seguito le produzioni, ma non può capire:

 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 

Qualcuno può aiutarmi a capire e risolvere questo problema?

Answer 1

La lingua L = {ai bj ck | i != j or j != k} può essere semplicemente scritta come L = L1 U L2 tale che L1 = {ai bj ck | i != j } e L1 = {ai bj ck | j != k }.

a L non v'è alcun vincolo sul simbolo c unica condizione è numberOf(a) non dovrebbe essere uguale a numberOf(b). In entrambi i numberof(a)>numberOf(b)onumberof(a)<. numberOf(b). Così la grammatica per questa lingua dovrebbe essere:

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

In grammatica sopra utilizzando E siamo in grado di generare lo stesso numero di a e b nel modello di anEbn, poi a convertire questo sentimentale da in forma frase sia E deve sostituito da B o A che genera una stringa nel formato tale che ai bj con i != j, utilizzando la variabile X qualsiasi numero di c può essere suffisso al modello ai bj.

Per capire questa grammatica leggere: Tips for creating Context free grammar e Why the need for terminals? Is my solution sufficient enough?

Allo stesso modo per L non v'è alcun vincolo sul simbolo a unica condizione è numberOf(b) non dovrebbe essere uguale a numberOf(c). In entrambi i numberof(b)>numberOf(c)onumberof(b)<. numberOf(c). Così la grammatica per questa lingua dovrebbe essere:

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

Ora utilizzando sia di questa grammatica un introducendo una nuova variabile inizio S e due nuove regole di produzione S => L1 | L2 che ottiene la grammatica per la lingua L = {ai bj ck | i != j or j != k}.