# Grammatiche

## Grammatiche monotone

- ogni produzione ha la forma $\alpha \to \beta$ dove $|\alpha| \leq |\beta|$
- Se si ammette $S \to \varepsilon$, però S non deve apparire in parti destre di produzioni

Equivalenti agli automi lineari, ovvero macchine di Turing con memoria finita (gli automi lineari terminano sempre).

## Grammatiche context free

- ogni produzione ha forma $\alpha \to\beta$ con $|\alpha| =1$

Equivalente agli automi a pila non deterministici
## Grammatiche regolari

- Ogni produzione ha forma $\alpha \to\beta$ dove $|\alpha|=1,\beta \in V_T.V_N \space \cup V_T$
- esempi:
1. $A \to a$
2. $A\to aB$
3. $A \to \varepsilon$

Equivalente agli automi a stati finiti:
- si pone $V_n = Q,\ V_t = I,\ S=<q_0>$
- Per ogni $\delta(q, i) = q'$ diciamo che $<q> \to i<q'>\in P$
- se $q' \in F$ aggiungiamo anche $<q> \to i \in P$

#### Gerarchia di Chomsky