Formalna Kontekst Gramatyka Darmowe Od język bezkontekstowy

Question

Jak darmowa gramatyka formalna kontekst być generowane na następującym języku:

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

Mam następujący produkcjach, ale nie może go zrozumieć:

 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 

Czy ktoś może mi pomóc zrozumieć i rozwiązać ten problem?

Answer 1

Język L = {ai bj ck | i != j or j != k} można napisać po prostu jako L = L1 U L2 w taki sposób, że L1 = {ai bj ck | i != j } i L1 = {ai bj ck | j != k }.

W L nie ma ograniczenia na symbol c Jedynym warunkiem jest numberOf(a) nie powinna być równa numberOf(b). Albo numberof(a)>numberOf(b)lubnumberof(a)<. numberOf(b). Więc gramatyki tego języka powinno być:

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

W powyższej gramatyki używając E możemy wygenerować równą liczbę a i b w strukturze anEbn, a następnie przekonwertować ten sentymentalny ze w formie zdanie albo E musi zastąpiona B lub A powoduje, że generowany jest ciąg znaków w takiej postaci, że ai bj z i != j, przy użyciu zmiennej dowolną liczbę c można dodać do wzorca ai bj.

Aby zrozumieć tę gramatykę przeczytać: Tips for creating Context free grammar i Why the need for terminals? Is my solution sufficient enough?

Podobnie dla L nie ma ograniczenia na symbol a Jedynym warunkiem jest numberOf(b) nie powinna być równa numberOf(c). Albo numberof(b)>numberOf(c)lubnumberof(b)<. numberOf(c). Więc gramatyki tego języka powinno być:

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

Teraz używając zarówno tej gramatyki wprowadzenie nowego startu zmienną S i dwa nowe zasady produkcji S => L1 | L2 my dostaje gramatyki dla języka L = {ai bj ck | i != j or j != k}.