reconnaître le type maximum de langage formel

Question

Actuellement, j'essaie d'apprendre et de comprendre les langages formels et la grammaire. Je comprends la hiérarchie de Chomsky mais j'ai trouvé une tâche où je ne sais pas comment ils ont trouvé la solution. La tâche est:

G=({S},{a,b},S,P) 
P={S->epsilon, S->aS, S->Sb} 

1. Quel est le type maximal de cette grammaire?
2. Quel est le type maximal de L(G)?

Je sais que la grammaire est de type 2, mais la réponse a été écrit que L(G) est de type 3.

Il semble qu'il y ait aussi un type 3 grammaire décrivant cette langue, mais comment voulez-vous savoir quel est le type maximal d'un langage formel? Y a-t-il un truc?

Answer 1

Je ne pense pas qu'il existe une façon simple et algorithmique de toujours dire quelle classe de langage est L(G); Je veux dire, en général, je pense qu'il y a des cas qui ne peuvent tout simplement pas être prouvés d'une manière ou d'une autre. Ceci à partir de l'incomplétude/indécidabilité, étant donné que les grammaires non restreintes peuvent coder l'arithmétique. C'est très ondulé. Heureusement, vous pouvez essayer de comprendre quelle est votre langue, vous pouvez transformer la grammaire pour essayer de forcer la grammaire à être plus simple, etc., mais cela ne garantit pas le succès.

Dans ce cas particulier, il n'est pas trop mal de savoir quelle est la langue, de la reconnaître et d'en écrire une grammaire.

S -> e 
S -> aS 
S -> Sb 

Toute chaîne dérivée de S peut commencer par un certain nombre de a s par S -> aS, et peut se terminer par un certain nombre de b s par S -> Sb. Nous pourrions faire l'hypothèse que le langage est a*b*, puis le prouver en montrant (1) L (G) est un sous-ensemble de b et (2) un b est un sous-ensemble de L (G).

(1) La preuve est par induction sur le nombre d'applications de S -> aS et S -> Sb. Cas de base: si aucune de ces conditions n'est appliquée, seule la chaîne e est dérivable. e est dans a*b*, de sorte que le cas de base est confirmé. Hypothèse d'induction: supposons que toute chaîne dérivée jusqu'à et y compris k applications de S -> aS et S -> Sb est en a*b*. Étape d'induction: nous montrons que toute chaîne dérivée utilisant k+1 applications de ces productions est également en a*b*. Toute chaîne dérivée dans les productions k+1 a une production dérivée en k en sautant la production k+1. C'est parce que les productions gardent les mêmes ensembles non-terminaux. Nous savons déjà que cette chaîne plus courte dérivée en k est en a*b*. Nous avons deux cas à considérer:

1. S -> aS: cela ajoute un a à l'avant de la chaîne plus courte a*b*, en gardant en a*b*.
2. S -> Sb: ceci ajoute un b à la fin de la chaîne la plus courte en a*b*, en le maintenant dans a*b*.

Puisque les deux cas garder la chaîne en a*b*, toutes les chaînes dérivées dans k+1 applications des productions sont en a*b* et, par induction, toutes les chaînes générées par la grammaire sont.

(2) Considérons une chaîne a^n b^m dans a*b*. Il est généré par la grammaire comme suit: n applications de A -> aS, m applications de B -> Sb, et une application de S -> e. Ainsi, toutes les chaînes de a*b* sont générées par la grammaire.