share: true
title: Klasifikace gramatik a jazyků
aliases: ["klasifikace gramatik", "klasifikace gramatiky", "klasifikace jazyků", "klasifikace jazyka"]
- Noam Chomsky
- Chomskyho klasifikace gramatik
- Dělí jazyky a gramatiky do tříd
Klasifikace jazyků
| Formální jazyk |
Gramatika |
Model výpočtu (automat) |
| 0. rekurzivně spočetné |
neomezené pravidlo |
Turingův stroj |
| 1. kontextové |
pravidlo má na obou stranách stejný kontext (např. ) |
lineární automat (TM s omezenou velikostí pásky) |
| 2. bezkontextové |
A -> (vlevo neterminál, na pravé straně může být cokoliv) |
zásobníkový automat |
| 3. regulární* |
regulární |
konečný automat |
*každá regulární je zároveň i bezkontextová, ale ne obráceně
Minimální deterministický konečný automat - nejefektivnější model výpočtu pro daný problém
Pumpování = rekurzivně vytvoření libovolně dlouhé posloupnosti
Klasifikace gramatik
Regulární gramatiky (RG)
- Na levé straně max. 1 , na pravé pouze nebo
- a zároveň není na pravé straně žádného z pravidel
- Prázdný jazyk lze generovat RG, tedy prázdný jazyk patří do všech tříd jazyků
- Pro každý konečný jazyk lze vyrobit regulární gramatiku, tedy každý konečný jazyk je i regulární
Bezkontextové gramatiky (BG)
- = cokoliv = libovolně dlouhý řetězec složený z terminálů i neterminálů
Kontextové gramatiky (KG)
- = tzv. kontext, tedy i může být cokoliv
- Neumí vygenerovat prázdný řetězec
- a zároveň není na pravé straně žádného z pravidel
Možnosti klasifikací gramatik
Gramatiky mohou splňovat více klasifikací najednou, ale jen tyto možnosti z toho vychází jako validní:
- NG
- BG, NG
- KG, NG
- BG, KG, NG
- RG, BG, KG, NG
- Gramatika, ve které existují pouze derivace nekonečné délky, generuje prázdný jazyk
Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25