ESPRESSIONI REGOLARI

Le espressioni regolari sono un formalismo per distinguere una particolare tipologia di grammatiche dove

• la stringa vuota $ϵ$ e un espressione regolare
• dato un alfabeto $A$ se $a\in A$ allora $a$ e un espressione regolare
• se $X$ e $Y$ sono espressioni regolari allora $X+Y$ (unione), $X\bullet Y$ (concatenazione), $X^{\ast }$, (chiusura) sono anch’esse espressioni regolari

ESPRESSIONI REGOLARI E GRAMMATICHE

Ogni espressione regolare coincide con una corrispondente grammatica regolare, rispetto a una grammatica di tipo 3, l’espressione regolare mostra cosa si ottiene da un linguaggio mentre la grammatica mostra il come si ottiene

PREVIOUS NEXT