Grammatiche e Linguaggi Flashcards
Capitolo 2/3 (9 cards)
Cosa si intende per alfabeto?
Un insieme finito e non vuoto di simboli è un alfabeto.
Cosa si intende per parola o stringa?
Una sequenza finita di simboli, x1,x2….xn dove ciascun xi, è preso da uno stesso alfabeto X.
Quando due stringhe sono uguali?
Due stringhe sono uguali se i loro caratteri, letti da sinistra a destra, coincidono.
Cosa rappresenta l’insieme X*?
X* è l’insieme di tutte le stringhe di lunghezza finita costruite sull’alfabeto X.
Cos’è la concatenazione di stringhe?
La concatenazione di due stringhe a, di lunghezza m, e b, di lunghezza n, è una stringa di m+n simboli. Dove i primi m simboli rappresentano a e i restanti n la stringa b.
Quali sono le proprietà della concatenazione?
È un’operazione binaria associativa, non commutativa e con elemento neutro, formando un monoide (X*,°).
Come è definita la potenza h-esima di una stringa a?
È definita come: λ se h=0, a * a^(h-1) altrimenti.
Cos’è un linguaggio formale?
Un linguaggio formale L su un alfabeto X è un sottoinsieme di X: L ⊆ X.
Cosa serve per generare un linguaggio formale?
- Un alfabeto terminale (X).
- Un insieme di simboli non terminali (V).
- Un simbolo iniziale (S).
- Un insieme di produzioni (P).
