Informatica Teorica Video

1. video 1

1.1. Alfabeto: Insieme non vuoto e finito di simboli

1.1.1. Una stringa su un Alfabeto sigma è una sequenza finita di simboli di sigma

2. Gerarchia di Chomsky

2.1. Tipo 0

2.2. Tipo 1: C.S.

2.3. Tipo 2: C.F.

2.3.1. Pumping Lemma per C.F.

2.3.2. Alberi di Derivazione

2.3.3. Proprietà di chiusura

2.3.3.1. chiusi per: unione,concatenazione, iterazione

2.3.3.2. non chiusi per: intersezione, complemento

2.3.4. Caratteristiche produzioni:

2.3.4.1. A->A|aA|aAb|epsilon

2.3.4.2. ammesse lambda produzioni

2.3.5. Grammatiche CF

2.3.5.1. Produzioni

2.4. Tipo 3: Regolari