Gauche-Linéaire et Droit-Linéaire des Grammaires

De la construction d'un équivalent Régulière de la Grammaire à partir d'une Expression Régulière

Tout d'abord, je commence par quelques règles simples à construire Régulière de la Grammaire(RG) de l'Expression Régulière(RE).

Je suis en train d'écrire des règles de Droit Linéaire de la Grammaire (en laissant comme un exercice d'écriture des règles similaires pour la Gauche Linéaire de la Grammaire)

REMARQUE: lettres majuscules sont utilisées pour les variables, et les petits pour les terminaux de la grammaire. NULL symbole est ^. Terme 'un nombre quelconque de" signifie zéro ou plusieurs fois, qui est l'étoile * fermeture.

[IDÉE DE BASE]

• SEUL TERMINAL: Si le feu est tout simplement e (e being any terminal), nous pouvons écrire G, avec une seule règle de production S --> e (où S is the start symbol), est un équivalent RG.

• De l'UNION de l'OPÉRATION: Si le RE est de la forme e + f, où les deux e and f are terminals, nous pouvons écrire G, avec deux règles de production S --> e | f, est un équivalent RG.

• CONCATÉNATION: Si le RE est de la forme ef, où les deux e and f are terminals, nous pouvons écrire G, avec deux règles de production S --> eA, A --> f, est un équivalent RG.

• STAR FERMETURE: Si le RE est de la forme e*, où e is a terminal et * Kleene star closure opération, on peut écrire les deux règles de production dans G, S --> eS | ^, est un équivalent RG.

• PLUS de FERMETURE: Si le RE est de la forme e⁺, où e is a terminal et + Kleene plus closure opération, on peut écrire les deux règles de production dans G, S --> eS | e, est un équivalent RG.

• ÉTOILES, FERMETURE SUR l'UNION: Si le RE est de la forme (e + f)*, où les deux e and f are terminals, on peut écrire trois règles de production dans G, S --> eS | fS | ^, est un équivalent RG.

• PLUS FERMETURE SUR l'UNION: Si le RE est de la forme (e + f)⁺, où les deux e and f are terminals, nous pouvons écrire les quatre règles de production dans G, S --> eS | fS | e | f, est un équivalent RG.

• STAR de FERMETURE SUR la CONCATÉNATION: Si le RE est de la forme (ef)*, où les deux e and f are terminals, on peut écrire trois règles de production dans G, S --> eA | ^, A --> fS, est un équivalent RG.

• PLUS de FERMETURE SUR la CONCATÉNATION: Si le RE est de la forme (ef)⁺, où les deux e and f are terminals, on peut écrire trois règles de production dans G, S --> eA, A --> fS | f, est un équivalent RG.

Assurez-vous que vous comprend toutes les règles ci-dessus, voici le tableau récapitulatif:

+-------------------------------+--------------------+------------------------+
| TYPE                          | REGULAR-EXPRESSION | RIGHT-LINEAR-GRAMMAR   |
+-------------------------------+--------------------+------------------------+
| SINGLE TERMINAL               | e                  | S --> e                |
| UNION OPERATION               | e + f              | S --> e | f            |
| CONCATENATION                 | ef                 | S --> eA, A --> f      |
| STAR CLOSURE                  | e*                 | S --> eS | ^           |
| PLUS CLOSURE                  | e+                 | S --> eS | e           |
| STAR CLOSURE ON UNION         | (e + f)*           | S --> eS | fS | ^      |
| PLUS CLOSURE ON UNION         | (e + f)+           | S --> eS | fS | e | f  |
| STAR CLOSURE ON CONCATENATION | (ef)*              | S --> eA | ^, A --> fS |
| PLUS CLOSURE ON CONCATENATION | (ef)+              | S --> eA, A --> fS | f |
+-------------------------------+--------------------+------------------------+

remarque: symbole e et f sont des terminaux, ^ est NULLE symbole, et S est le début de la variable

[RÉPONDRE]

Maintenant, nous pouvons venir à votre problème.

a) (0+1)*00(0+1)*

Langue de description: Toutes les chaînes composé de 0 et de 1, contenant au moins une paire de 00.

• Droit Linéaire De La Grammaire:

  S --> 0 | 1S | 00A
  
  Un --> 0A | 1A | ^

  Chaîne peut commencer avec n'importe quelle chaîne de 0s et 1s c'est pourquoi comportait des règles s --> 0S | 1S et Parce que au-moins une paire de 00 ,il n'est pas null symbole. S --> 00A est inclus parce que 0, 1 peut être après 00. Le symbole A prend soin de 0 et de 1 après la 00.

• Gauche Linéaire De La Grammaire:

  S --> S0 | S1 | A00
  
  Un --> A0 | A1 | ^

b) 0*(1(0+1))*

Langue de description: n'Importe quel nombre de 0, suivi de 10 et 11.

{ parce que 1(0 + 1) = 10 + 11 }

• Droit Linéaire De La Grammaire:

  S --> 0 | UN | ^
  
  Un --> 1B
  
  B --> 0A | 1A | 0 | 1

  Chaîne de caractères commence par un nombre quelconque de 0 ainsi la règle S --> 0S | ^ sont inclus, alors la règle pour générer 10 et 11 pour un certain nombre de fois à l'aide d' A --> 1B and B --> 0A | 1A | 0 | 1.

  Autre alternative à droite linéaire de la grammaire peut être

  S --> 0 | UN | ^
  
  Un --> 10A | 11A | 10 | 11

• Gauche Linéaire De La Grammaire:

  S --> A | ^
  
  Un --> A10 | A11 | B
  
  B --> B0 | 0

  Une forme alternative peut être

  S --> S10 | S11 | B | ^
  
  B --> B0 | 0

c) (((01+10)*11)*00)*

Langue de description: Première est la langue contient une valeur null(^) en chaîne, car il y a une * (étoile) sur l'extérieur de chaque chose présents à l'intérieur (). Aussi, si une chaîne de caractères dans la langue n'est pas null qui d'un air de défi se termine par 00. On peut simplement penser à cette expression régulière en la forme de ( ( (A)* B )* C ) * (A)* (01 + 10)* qui est le nombre de répétition de 01 et 10.
Si il y a un exemple d'Une chaîne, il y aurait un B d'un air de défi, parce que (A)*B et B est de 11.

Quelques exemples de chaînes de caractères { ^, 00, 0000, 000000, 1100, 111100, 1100111100, 011100, 101100, 01110000, 01101100, 0101011010101100, 101001110001101100 ....}

• Gauche Linéaire De La Grammaire:

  S --> A00 | ^
  
  Un --> B11 | S
  
  B --> B01 | B10 | A

  S --> A00 | ^ parce que toute chaîne est null, ou si ce n'est pas la valeur null, il se termine par un 00. Lorsque la chaîne se termine avec 00, la variable A correspond au modèle ((01 + 10)* + 11)*. De nouveau, ce modèle peut être null ou doit se terminer par 11. Si sa valeur est null, alors A matchs avec S de nouveau je.e la chaîne se termine avec motif comme (00)*. Si le motif n'est pas null, B matchs avec (01 + 10)*. Lorsque B correspond à tout ce qu'il peut, A commence correspondant à la chaîne de nouveau. Cela ferme la plus * dans ((01 + 10)* + 11)*.

• Droit Linéaire De La Grammaire:

  S --> A | 00S | ^
  
  Un --> 01A | 10A | 11S

Deuxième partie de votre question,:

For a) I have the following:
Left-linear
S --> B00 | S11
B --> B0|B1|011

Right-linear
S --> 00B | 11S
B --> 0B|1B|0|1

(réponse)

Vous solution sont mauvais pour les raisons suivantes,

Gauche-linéaire de la grammaire est mauvaise Parce chaîne 0010 pas possible de générer.
Droit-linéaire de la grammaire est mauvaise Parce chaîne 1000 n'est pas possible de générer. Bien que les deux sont dans le langage généré par l'expression régulière de la question (a).

MODIFIER

L'ajout de l'IFD pour chaque expression régulière. de sorte qu'on peut le trouver utile.

a) (0+1)*00(0+1)*

b) 0*(1(0+1))*

c) (((01+10)*11)*00)*

Dessin DFA pour cette expression régulière est truc et complexe.

_{Pour cela, j'ai voulu ajouter des DFA}

Pour simplifier la tâche, il nous faut réfléchir sur la nature de la formation de RE
pour moi, la RE (((01+10)*11)*00)* ressemble (a*b)*

(((01+10)*11)* 00 )*
(          a*   b )*

Réellement dans l'expression ci-dessus a de soi dans la forme de (a*b)*
c'est ((01+10)*11)*

RE (a*b)* est égal à (a + b)*b + ^. La DFA (unb) est comme belows:

DFA pour ((01+10)*11)* est:

DFA pour (((01+10)*11)* 00 )* est:

_{Essayer de trouver une similitude dans la construction de plus de trois DFA. ne pas aller de l'avant jusqu'à ce que vous ne comprenez pas premier}

OriginalL'auteur