Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Chomského hierarchie

Definice (Přepisovací systém)

Přepisovací (produkční) systém je dvojice , kde je konečná abeceda a množina přepisovacích pravidel (uspořádaných dvojic prvků z ). Slovo se přímo přepíše na ( ), pokud . Derivace (odvození) je zřetězení několika přímých přepsání.

Definice (Generativní gramatika)

Generativní gramatika je čtveřice , kde je množina neterminálních symbolů, množina terminálních symbolů, startovací symbol () a množina pravidel. Jazyk generovaný gramatikou je .

Definice (Chomského hierarchie)

Chomského hierarchie je rozdělení gramatik do 4 tříd podle omezení na pravidla:

- G0 (Rekurzivně spočetné jazyky) mohou mít obecná pravidla.
- G1 (Kontextové jazyky/gramatiky) - jen pravidla tvaru , kde a , navíc . Může obsahovat i pravidlo , ale pak se nesmí vyskytovat na pravé straně žádného pravidla.
- G2 (Bezkontextové jazyky/gramatiky) - jen pravidla tvaru , kde , .
- G3 (Regulární jazyky/pravé lineární gramatiky) - jen pravidla typu a , kde a .

Definuje uspořádání tříd jazyků podle inkluze, tedy .

Poznámka

S nastává problém, protože bezkontextové gramatiky umožňují pravidla tvaru . Řešením je převod na nevypouštějící bezkontextové gramatiky - takové bezkontextové gramatiky, které nemají pravidla typu .

Věta (o nevypouštějících bezkontextových gramatikách)

Ke každé bezkontextové existuje nevypouštějící bezkontextová tak, že

Je-li , pak , t.ž. a jediné pravidlo v s na pravé straně je a není v na pravé straně žádného pravidla.

Poznámka (Lineární gramatiky)

Pro každou gramatiku typu G3 lze sestrojit konečný automat, který přijímá právě jazyk jí generovaný, stejně tak pro každý konečný automat lze sestrojit gramatiku G3. Levé lineární gramatiky také generují regulární jazyky, díky uzavřenosti na reverzi. Lineární gramatiky, s pravidly typu , kde , generují lineární jazyky - silnější než regulární jazyky.

Definice (Separovaná a nevypouštějící gramatika)

Separovaná gramatika je gramatika (obecně libovolné třídy), obsahující pouze pravidla tvaru , kde buď , nebo a . Nevypouštějící (monotónní) gramatika (také se neomezuje na konkrétní třídu) je taková, že pro každé pravidlo platí .

Poznámka (Kontextové gramatiky)

Ke každé kontextové gramatice lze sestrojit ekvivalentní separovanou. Ke každé monotónní gramatice lze nalézt ekvivalentní kontextovou.