Grammatica regolare: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
→Definizione: descrizione sbagliata della formula.. semplicemente erano invertite. per verifica vedere "Introduction to the theory of computation" di Michael Sipser |
m Bot: Fix tag <math> |
||
Riga 6:
{{vedi anche|grammatica formale}}
Come le altre grammatiche formali, è una [[N-pla|quadrupla]] <math>\mathcal{G} = \left \langle N, \Sigma, P, S \right \rangle</math>, in cui
#<math>N
#<math>\Sigma
#<math>S \in N</math> detto ''assioma'' è il simbolo non terminale di inizio.
#<math>P
#:questa scrittura ci dice che a sinistra ci deve essere almeno un non terminale ed a destra qualsiasi cosa.
Riga 36:
== Esempi ==
Un esempio di grammatica lineare destra <math>\mathcal{G}</math> con <math>N = \{S\}, \Sigma = \{a, b\}, S
: <math>S \to aS</math>
: <math>S \to b</math>
Questa grammatica descrive lo stesso linguaggio dell'[[espressione regolare]] <math>a^*b</math>.
Un altro esempio di grammatica lineare destra <math>\mathcal{G}</math> con <math>N = \{S, C\}, \Sigma = \{a, b, c\}, S
: <math>S \to aS</math>
: <math>S \to bC</math>
Riga 50:
=== Esempio di grammatica non regolare ===
Una grammatica che genera il linguaggio <math>L = \{a^ib^i\; |\; i \ge 0\}</math> può essere <math>\mathcal{G}</math> con <math>N = \{S, A\}, \Sigma = \{a, b\}, S
: <math>S \to aA</math>
: <math>A \to Sb</math>
| |||