Grammatica regolare
Da Wikipedia, l'enciclopedia libera.
Una grammatica lineare, spesso chiamata grammatica regolare, è una grammatica formale (N, Σ, P, S) le cui produzioni (P) sono nella forma:
- nel caso di lineari destre (in inglese right regular grammar)
- A → a - dove A è un simbolo non terminale di N e a è un simbolo terminale di Σ
- A → aB - dove A e B sono in N e a è in Σ
- A → ε - dove A è in N.
- nel caso di lineari sinistre (in inglese left regular grammar)
- A → a - dove A è un simbolo non terminale di N e a è un simbolo terminate in Σ
- A → Ba - dove A e B sono in N e a è in Σ
- A → ε - dove A è in N.
Un esempio di grammatica lineare destra G con N = {S, A}, Σ = {a, b, c}, P formato dalle seguenti regole di produzione:
- S → aS
- S → bA
- A → ε
- A → cA
e S è il simbolo iniziale. Questa grammatica descrive lo stesso linguaggio dell'espressione regolare a*bc*.
Le grammatiche lineari descrivono esattamente tutti i linguaggi lineari (o regolari) e in questo senso sono equivalenti agli automi a stati finiti e alle espressioni regolari. Inoltre, le grammatiche lineari destre sono uguali loro stesse a linguaggi regolari, come lo sono le grammatiche lineari sinistre.
Ogni grammatica lineare è una grammatica context-free.
Ogni grammatica context-free può essere facilmente riscritta nella forma in cui sono usate solo combinazione di produzioni lineari destre e lineari sinistre. Quindi, queste grammatiche possono essere esprimere linguaggi context-free. Le grammatiche lineari, che usano le produzioni o lineari sinistre o lineari destre, ma non entrambe, possono esprimere solo un insieme più piccolo di linguaggi, chiamati linguaggi regolari. In questo senso sono equivalenti agli automi a stati finiti e alle espressioni regolari. (per chiarimento: li linguaggio context-free con stringhe nella forma aibi è generato dalla grammatica G con N = {S, A}, Σ = {a, b}, P con le produzioni
- S → aA
- A → Sb
- S → ε
e S simbolo iniziale. Nota che questa grammatica ha entrambe le produzioni, regolari destre e sinistre, e quindi non è regolare.)
Questo tipo di grammatiche restringe le sue regole ad un singolo simbolo non terminale nel lato sinistro della produzione e nel lato destro un singolo simbolo terminale, possibilmente seguito (o preceduto, ma non entrambe le forme nella stessa grammatica) da un singolo simbolo non terminale.
Alcuni libri di testo e articoli non ammettono regole diproduzione vuote, e assumono che la stringa vuota non sia presente nel linguaggio.
Tali grammatiche formano una classe detta delle grammatiche di tipo 3 nella gerarchia di Chomsky.
[modifica] Voci correlate
| Teoria degli automi: linguaggi formali e grammatiche formali | |||
|---|---|---|---|
| gerarchia di Chomsky |
Grammatiche | Linguaggi | automa minimo |
| Tipo-0 | (illimitato) | Ricorsivamente enumerabile | Macchina di Turing |
| (illimitato) | Ricorsivo | Decider | |
| Tipo-1 | Sensibile al contesto | Sensibile al contesto | Lineare-limitato |
| Tipo-2 | Context-free | Context-free | Automa a pila |
| Tipo-3 | Lineare (o Regolare) | Lineare (o Regolare) | A stati finiti |
| Ciascuna categoria di linguaggio o grammatica è un sottoinsieme del proprio sovrainsieme di categoria direttamente sottostante. | |||
