this dir | view | cards | source | edit | dark
top
- přepisovací pravidla (Li,Pi)
- množina terminálů VT a neterminálů VN
- ve výsledných slovech jsou jen terminály
- gramatiky generují jazyky
- automaty kontrolují, zda slovo patří do jazyka
- Chomského hierarchie
- L0 gramatiky
- normální forma
- αχβ→αγβ
- α,γ,β∈(VN∪VT)∗
- χ∈VN
- L1 monotónní gramatiky
- ∣Li∣≤∣Pi∣
- slova se nemůžou zkracovat
- deklarace λ∈L
- kde λ je prázdné slovo
- normální forma
- αχβ→αγβ
- α,β∈(VN∪VT)∗
- γ∈(VN∪VT)+
- χ∈VN
- L2 bezkontextové gramatiky
- ∣Li∣=1
- Chomského normální forma
- X→YZ∣a
- X,Y,Z∈VN
- a∈VT
- tzn. na levé straně jeden neterminál, na pravé straně dva neterminály nebo jeden terminál
- navíc tam patří prázdné slovo (tzn. deklarujeme λ∈L)
- lze obejít složitým způsobem (bez deklarace)
- L3 regulární gramatiky
- X→Yw∣w
- X,Y∈VN
- w∈VT∗
- normální forma
- X→Ya∣λ
- X,Y∈VN
- a∈VT
- možná lepší varianta je místo Yw uvažovat wY apod.
- chceme ukázat L3⊊L2⊊L1⊊L0
- zjevně L3⊆L2
- pro L2⊆L1
- máme
- X→λ∣a
- Y→XZb
- převedeme na
- X→a
- Y→XZb∣Zb
- (vyškrtli jsme X→λ)
- to nestačí
- mohli bychom se zacyklit
- budeme si značit, které neterminály už jsme vyškrtli
- nebo to můžeme udělat najednou (poznačíme si všechny levé strany, které mají napravo λ)
- zjevně L1⊆L0
- k ostrosti se vrátíme
- automaty
- kontrolují, že na vstupu je slovo z gramatiky
- (3) konečné automaty
- automatu odpovídá jazyk, který dostaneme ze všech slov, které začínají v šipkách dovnitř a končí v šipkách ven
- deterministický vs. nedeterministický
- přechodové hrany s písmenky
- slovo rozložíme na několik hran
- prázdné slovo vyřešíme zdvojením šipek
- X→aY v automatu zapíšeme jako XaY
- (2) zásobníkové automaty
- přepisovací pravidla lze zapisovat jako strom a číst listy v inorder pořadí
- fungují nedeterministicky
- (1) Turingovy stroje, které se nepohybují mimo vstupní pásku
- běžíme proti směru generování – zkracuje se to
- (0) Turingovy stroje
- separované gramatiky
- na levé straně se nesmí vyskytovat terminály nebo musí vyskytovat aspoň jeden neterminál
- to se dá zařídit tak, že terminál a nahradíme terminálem a a přidáme další přepisovací pravidlo a→a