Hierarchia Chomsky ego
Języki typu 3 - regularne
Produkcje gramatyki mają postać: A aB|a, gdzie A, B " N i a " T .
Hierarchia Chomsky ego
Języki typu 2 - bezkontekstowe
Języki formalne i techniki translacji - Wykład 13
Produkcje gramatyki mają postać: A ą, gdzie A " N i ą " (N *" T )".
Języki typu 1 - kontekstowe
Maciek Gębala
Produkcje gramatyki majÄ… postać: Ä… ², gdzie Ä…, ² " (N *" T )",
a
Ä… = µ i |Ä…| |²|.

a
WyjÄ…tkowo dopuszczamy produkcjÄ™ S S |µ, gdzie S jest symbolem
22 maja 2013
początkowym i nie występuje w żadnej innej produkcji.
Języki typu 0 - nieograniczone (rekurencyjnie przeliczalne)
Produkcje gramatyki majÄ… postać: Ä… ², gdzie Ä…, ² " (N *" T )"
i Ä… = µ.

Maciek Gębala Hierarchia Chomsky ego Maciek Gębala Hierarchia Chomsky ego
Języki nieograniczone Języki kontekstowe - przykład
Język
L = { ww : w " {0, 1}" }
Języki nieograniczone (definiowane gramatykami nieograniczonymi)
są równoważne językom rozpoznawanym przez maszyny Turinga.
Zgodnie z tezą Church-a języki rozpoznawalne przez TM są tymi Lemat
które można obliczyć.
Język L nie jest bezkontekstowy.
Zagadnienia obliczalności będą poruszane na wykładzie Teoria Dowód
obliczeń i złożoność obliczeniowa.
Na tablicy.
Maciek Gębala Hierarchia Chomsky ego Maciek Gębala Hierarchia Chomsky ego
Języki kontekstowe - przykład Języki kontekstowe - przykład
Gramatyka kontekstowa dla języka L
S A|µ
A 0ZA|1JA|0K |1L
Jak wyprowadzić 110110
Z 0 0Z
S A 1JA 1J1JA 1J1J0K
Z 1 1Z
1J10JK 11J0JK 110JJK
J0 0J
110JL0 110L10 110110
J1 1J
ZK K 0
JK L0
Pytanie: czy można wyprowadzić słowo z poza języka?
ZL K 1
JL L1
K 0
L 1
Maciek Gębala Hierarchia Chomsky ego Maciek Gębala Hierarchia Chomsky ego
Gramatyka kontekstowa a automat Gramatyki dowolne
Przykład - L = { 1n : "i"N n = 2i }
Gramatyka dowolna
Czy istnieje automat rozpoznający języki kontekstowe?
S AS|1K
A1 11A
Automat liniowo ograniczony
AK K
Automat z wejściem na taśmie który może poruszać się tylko na tym
K µ
wejściu (w obie strony) i zmieniać zawartość taśmy. Automat
niedeterministycznie odwraca proces wyprowadzenia.
Równoważna gramatyka kontekstowa
S AS|K
Czy można stworzyć automat w pełni deterministyczny?
A1 11A
AK 1K
K 1
Prawie wszystkie  rozsądne języki są kontekstowe.
Maciek Gębala Hierarchia Chomsky ego Maciek Gębala Hierarchia Chomsky ego
Relacje między typami języków
Twierdzenie: Języki typu i + 1 są ściśle zawarte w językach typu i.
Dowód:
i = 2 - każda gramatyka regularna jest bezkontekstowa
i istnieją języki bezkontekstowe nie będące
regularnymi, np. palindrom;
i = 1 - gramatyka bezkontekstowa w postaci Chomsky ego
jest gramatyką kontekstową, przykład z wykładu jest
językiem kontekstowym a nie jest bezkontekstowym;
i = 0 - każda gramatyka kontekstowa jest gramatyką
dowolną, dowód ścisłości zawierania wykracza poza
ramy obecnego wykładu.
Maciek Gębala Hierarchia Chomsky ego