Création de grammaires sans contexte pour les langues

Question

Je prends une classe sur Automate fini. Je me prépare pour un semestre et j'ai du mal à créer des grammaires pour des langues spécifiques. Bien que je trouve les plus simples très intuitifs, quand ils deviennent plus complexes, je ne sais pas par où commencer. Par exemple:

L = {w E {a, b, c} *: nb (w) = na (w) + nc (w)}

La réponse est:

S → S1 | S2
S1 → bS3 | S3b | S3bS3
S3 → S0 | S1
S2 → XS4 | S4X | S4XS4
S4 → S | S2
S0 → bS0XS0 | XS0bS0 | e
X → a | c

Si quelqu'un pouvait me donner un petit conseil sur le processus de pensée impliqué, il serait grandement apprécié.

Answer 1

La langue que vous avez indiquée n'est pas claire. Je suppose w E {a,b,c}* signifie w ε {a,b,c}* et nb(w) != na(w) + nc(w) signifie que toutes les chaînes dans la langue ont un nombre de b n'est pas égal à la somme du nombre de a et le nombre de c.

Si tel est le cas, vous devez penser aux caractéristiques de toutes les chaînes qui seront dans la langue, et à toutes les caractéristiques qui excluront une chaîne d'être dans cette langue.

Cette langue accepte les chaînes où le nombre de b est =/= le nombre de a + nombre de c. Nous pouvons reformuler cette langue pour être celui qui accepte les chaînes qui:

nombre a 's + numéro c' s> nombre de b ' OU s Numéro a' s + numéro 'numéro < de b' c s

Ceci explique le premier S -> S1 | S2

S1 assure qu'il y a au moins une b (S3), et oblige alors soit une quantité égale de b 's en tant que a' s et c 's (S0) ou plus b' s que a « s et c (S1). Le résultat net de la règle S1 est une chaîne avec plus de b que a et c. S2 s'assure qu'il y a plus de a et/ou c que de b. Il le fait en forçant un a ou c (X), puis en autorisant une quantité égale de a 's/c (S0) ou plus a' s/c 's que b (S2 à nouveau).

Ceci est spécifique à votre exemple, mais vous pouvez voir genre de la façon dont le processus de pensée qui va dans la création de cette grammaire:

1. Formulez la langue comme des cas concrets (a « s/c » s> ou < b « s)
2. pour chacun des cas, commencez par vous assurant que le cas tiendra (force # b » s> que a « s/c » s en forçant au moins un b) puis en élargissant la chaîne à inclure toutes les possibilités d'égal ac et b, ou moins a 's/c' s que b 's.
3. Manipulez symétriquement l'autre boîtier.

Le problème est que vous devez vous assurer que chaque chaîne de la langue est générée et que toutes les chaînes qui ne sont pas dans la langue ne sont pas générées. (relire ceci jusqu'à ce que son implication coule dedans)