rivediamo alcuni concetti noti e introduciamo convenzioni notazionali comuni nella teoria dei linguaggi formali:

• Σ : un alfabeto (insieme di simboli), di solito finito
• Σ* : il monoide delle stringhe su Σ
• ε : la stringa vuota, elemento neutro del monoide
• _ _ : concatenazione di stringhe (operatore binario infisso "invisibile")
• Σ+ = Σ*\{ε} : il semigruppo delle stringhe non vuote su Σ
• |_| : lunghezza di una stringa (definibile per induzione... su che cosa?)
• Σn : l'insieme delle stringhe su Σ di lunghezza n

altre operazioni e proprietà facilmente definibili (ad es. per induzione sulla lunghezza):

• inversa x^R di una stringa x
• prefisso x di una stringa xy, proprio se y ≠ ε
• suffisso y di una stringa xy, proprio se x ≠ ε
• sottostringa y di una stringa xyz, propria se xz ≠ ε

un linguaggio L sull'alfabeto Σ è un insieme di stringhe su Σ:   L ⊆ Σ*

• esempi: ∅, Σ, Σ*, Σ+, {ε}, { x ∈ Σ*| x è palindroma }, ...

operazioni sui linguaggi (su un alfabeto Σ):

• le operazioni booleane standard di ogni algebra di insiemi
  • unione, intersezione, complemento, differenza, ...
• concatenazione:  LL' = { xy | x ∈L, y ∈L' }
  • (se gli alfabeti di L, L' sono diversi, quello di LL' ne è l'unione)
• chiusura di Kleene:  L^* = { x | x ∈ Lⁿ, n ≥ 0 }
  • dove le iterate della concatenazione sono induttivamente definite:
  • L⁰ = { ε } ,   Lⁿ⁺¹ = LⁿL = L Lⁿ
• chiusura positiva:  L⁺ = L^* \L⁰

perché estendere le operazioni delle stringhe ai linguaggi?

• ciò è utile nella trattazione algebrica delle grammatiche, dove un simbolo non terminale può essere visto come la designazione di un insieme di stringhe (cioè un linguaggio) sull'alfabeto terminale, mentre un simbolo terminale designa il singoletto che lo contiene

le algebre di interesse a tal fine sono note come algebre di Kleene

proprietà di frequente interesse di linguaggi, ad es. nella codifica dell'informazione, sono le seguenti, raccolte in una sola definizione:

• un linguaggio L gode della proprietà prefissa (suffissa) se nessuna stringa del linguaggio è un prefisso (suffisso) proprio di un'altra stringa del linguaggio

esempio:

• il linguaggio L = {a ⁱ b | i ≥ 0 } gode della proprietà prefissa, ma non della proprietà suffissa

si tratta di strutture matematiche atte alla definizione generativa di linguaggi formali

• si è già vista la definizione di grammatica libera G_L = (V_T, V_N, P, s₀), quale struttura di generazione del linguaggio L

una classe più generale di grammatiche, che generano una più ampia classe di linguaggi, si ha dalla definizione di grammatica libera ammettendo nella parte sinistra delle produzioni, invece che solo un simbolo non terminale, una stringa sull'alfabeto V_T ∪ V_N che contenga almeno un simbolo non terminale

• resta valida la condizione che il simbolo iniziale s₀ sia un elemento di V_N, nonché la definizione di L, linguaggio generato da G_L, quale sottoinsieme di V_T^* costituito dalle stringhe terminali derivabili da s₀ con le produzioni P

quest'ultima proprietà è definita come segue: siano α, β, γ, δ stringhe di V_T ∪ V_N :

• derivazione diretta  ⇒_G :    αβγ ⇒_G αδγ se β→δ ∈ P
• derivazione  ⇒_G^* : chiusura riflessiva e transitiva della derivazione diretta

convenzioni notazionali: d'ora innanzi designiamo con

• T : l'alfabeto (o vocabolario) terminale
• N : l'alfabeto (o vocabolario) non terminale
• lettere maiuscole A,B,C,...: simboli non terminali
• lettere minuscole iniziali a,b,c,...: simboli terminali
• lettere minuscole finali u,v,w,x,y,z,...: stringhe su T
• lettere minuscole greche α,β,γ,δ,...: stringhe su T ∪ N

problema: trovare una grammatica che generi il linguaggio {aⁿbⁿcⁿ | n ≥ 0}

soluzione: con N = {A,B,C} e s₀=A, la grammatica che ha le seguenti produzioni:

classificazione di Chomsky delle grammatiche, per restrizioni crescenti sulla forma delle produzioni α→β :

• tipo 0, o unrestricted : nessuna restrizione
• tipo 1, o context-sensitive : |α| ≤ |β|
• tipo 2, o context-free : |α| = 1
• tipo 3, o right-linear : |α| = 1, β ∈ T^* ∪ T^*N

si rammenti che α deve sempre contenere almeno un simbolo di N

• ne consegue che ε non è derivabile con grammatiche di tipo 1, mentre può esserlo con quelle degli altri tipi

se si escludono le produzioni aventi β=ε, le suddette classi di grammatiche sono ordinate da inclusione propria, così come lo sono le corrispondenti classi di linguaggi da esse generabili, ai quali si applica la stessa terminologia

• due grammatiche si dicono equivalenti se generano lo stesso linguaggio

le grammatiche di tipo 1 devono il loro nome al fatto di avere sempre una grammatica equivalente le cui produzioni sono della forma γAδ→γβδ, con A∈N e β non vuota

data una grammatica G, il problema di decisione del linguaggio L_G consiste nel determinare se, data una stringa x sul suo alfabeto terminale, x ∈ L_G

• un riconoscitore è (un modello matematico di) una procedura di calcolo per risolvere il problema di decisione di un linguaggio

costituenti essenziali dei riconoscitori:

• Q : un insieme (finito) di stati, fra i quali:
• q₀∈Q : uno stato iniziale
• F⊆Q : un insieme di stati finali, o accettanti
• δ : una dinamica, che determina le transizioni di stato ed eventuali altre azioni del riconoscitore in base all'input e allo stato corrente

un automa a stati finiti (FSA) non ha altri costituenti, e la sua dinamica è limitata alle transizioni di stato e alla lettura sequenziale dell'input

• un FSA è deterministico (DFA) se la sua dinamica assegna al più uno stato (di arrivo) alla transizione determinata dallo stato corrente e da un simbolo in input, altrimenti è non deterministico (NFA)

ulteriori costituenti, e altre possibilità di azione oltre alle transizioni di stato, caratterizzano classi di riconoscitori più sofisticati degli automi:

• possibilità di spostamento bidirezionale del dispositivo di lettura sul supporto dell'input ("nastro")
• possibilità di scrittura sul nastro
• disponibilità di una memoria ausiliaria

un riconoscitore accetta una stringa x in input se la sua dinamica permette una sequenza di transizioni dallo stato iniziale a un stato accettante

• il linguaggio definito da un riconoscitore è l'insieme delle stringhe che accetta

le classi di linguaggi definite nella gerarchia di Chomsky possono essere caratterizzate in base alle caratteristiche di corrispondenti classi di riconoscitori:

• tipo 3: automi a stati finiti
• tipo 2: automi con pila (pushdown automata (PDA)
• tipo 1: automi linear bounded
• tipo 0: macchine di Turing