Grammaire sans contexte avec au moins une étoile Kleene

Question

J'essaie de créer la grammaire sans contexte qui génère toutes les expressions régulières sur {a, b} avec au moins une étoile Kleene. Ce que je l'ai fait jusqu'à présent est la suivante:

S ::= A + S | A 
A ::= B . A | B 
B ::= T | B* | (S) 
T ::= a | b | eps 

Je suppose que cela peut générer toutes les expressions régulières, mais ce que je ne peux pas obtenir ma tête est autour de la façon de la définir de manière à ce qu'au moins un Kleene étoiles doit être dans cette expression.

Answer 1

Le problème est typique des machines d'état, dans lesquelles il y a un état initial, et un état "passe". La solution consiste à avoir des côtés droits correspondant à chaque état. Je vais utiliser le numéro 2 pour les règles qui représentent les états passants.

S ::= S2 

S2 ::= A + S2 | A2 + S1 | A2 
A2 ::= B2 . A | B . A2 | B2 
B2 ::= B* | (S2) 

S1 ::= A + S1 | A 
A ::= B . A | B 
B ::= T | B* | (S1) 
T ::= a | b | eps 

Les expressions de passage sont définies en termes de passage de sous-expressions. Ainsi, la grammaire générera toujours une fermeture à gauche ou à droite d'une expression.