Grammaire en context for {a * b * c *} - {a^n b^n c^n | n> = 0}

Question

J'ai des problèmes avec ce problème. Je crois qu'il me dit qu'aucune chaîne ne peut être générée avec un nombre pair de b et c. Ceci est dû à la soustraction du second ensemble.

Une bonne chaîne provenant d'un CFG nouvellement formé doit être quelque chose comme aaabbc ou abbbcc et ainsi de suite.

donc j'ai essayé briser le problème en trois parties ...

1. états simples

   a.) S(1) -> aS(1) | a |^
   b.) S(2) -> bS(2) | b |^
   c.) S(3) -> cS(2) | b |^
   

2. Deux États

   a.) S(4) -> aS(4)b | S(1) | S(2) 
   b.) S(5) -> bS(5)c | S(2) 
   c.) S(6) -> aS(6)c | S(3) | S(1) 
   

3. États Etats w/AB

   a.) S(7) -> S(1) | S(4)S(6) 
   b.) S(8) -> S(2) | S(5)S(6) 
   c.) S(9) -> S(3) | S(6)S(3) 
   

   avec un état de orginal commencer ...

   S -> S(7) | S(8) | S(9) 
   

Cependant, je vais avoir des problèmes de construction des chaînes comme aaaabbbcc ...

Suis-je tort GFR la formation? Je me sentais comme si j'étais sur la bonne voie mais maintenant je suis complètement perdu.

Answer 1

Je divisé le problème en 2 sous problèmes

Le nombre de c'est différent du nombre de années b. Par conséquent, les a et c ou b et c peuvent être les mêmes.

Le nombre de b est différent du nombre de c. Par conséquent, les a et b ou a et c peuvent être les mêmes.

Modifier: Plus formellement comme indiqué par Rici {a ⁿ b ^m c ^* | n ≠ m} {a ∪ ^* b ⁿ c ^m | n ≠ m}

//a and b is different 
S-->XR 
//b and c is different 
S-->DY 

//Genarates a string where a is more than b 
X--> aXb | A 
A --> aA | a 

//Genarates a string where b is more than a 
X--> bXa | B 
B --> bB | b 

//Genarates a string where b is more than c 
Y--> bYc | B 
B --> bB | b 

//Genarates a string where c is more than b 
Y--> cYb | C 
C --> cC | c 

R-->Rc|c|^ 
D-->Da|a|^ 

Answer 2

Une expression plus simple pour cette langue est:

{a ⁿ b ^m c ^* | n ≠ m} {a ∪ ^* b ⁿ c ^m | n ≠ m}

(Utilisation de l'étoile de Kleene ci-dessus est probablement un abus de notation. A l'origine, je l'ai écrit avec une troisième variable entière. Mais je pense que l'étoile est plus claire.)

Maintenant, {a ⁿ b ^m | n ≠ m} est simplement un ⁿ (un ⁺ | b ⁺) b ⁿ

Ainsi, la pleine expression peut être écrite comme ⁿ (un ⁺ | b ⁺) b ⁿ c ^* | un ^* b ⁿ (b ⁺ | c ⁺) c ⁿ

Mettre tout cela ensemble dans un CFG est un peu fastidieux je l'ai laissé ainsi pour le lecteur. Mais c'est totalement mécanique. Rendre un DFA (ou plus correctement Deterministic Pushdown Automaton) à partir de cela peut être plus délicat, puisque le CFG est ambigu. En fait, chaque CFG pour cette langue est ambigu. Mais il n'y a aucun problème à faire une NDPA.