Studijní materiály

Zpět

Hromadně přidat materiály

Předtermin_21_05_2008

IB005 - Formální jazyky a automaty I

Hodnocení materiálu:

Zjednodušená ukázka:

Stáhnout celý tento materiál

a L a X je takov´a podmnoˇzina
jazyka L, kter´a je nadmnoˇzinou mnoˇziny K. Pak X je regul´arn´ı jazyk.
(b) Bud’ R nˇej´ak´a prav´a kongruence s nekoneˇcn´ym indexem na mnoˇzinˇe vˇsech slov nad
danou abecedou a L sjednocen´ım vˇsech tˇr´ıd rozkladu podle R. Pak L jistˇe nen´ı regul´arn´ı
jazyk.
(c) Nejmenˇs´ı tˇr´ıda jazyk˚u obsahuj´ıc´ı vˇsechny koneˇcn´e jazyky a je uzavˇren´a na operace
sjednocen´ı, zˇretˇezen´ı a pr˚unik odpov´ıd´a pr´ave tˇr´ıdˇe regul´arn´ıch jazyk˚u.
(d) Bezkontextov´a gramatika bez lev´e rekurze generuje jazyk, kter´y nen´ı rekurzivn´ı.
(e) D´elka odvozen´ı slova d´elky n,n≤0 pomoc´ı pravidel v Greibachov´e norm´aln´ı formˇe je
vˇzdy rovna 2n + 1.
(f) Tˇr´ıda vˇsech jazyk˚u akceptovateln´ych deterministick´ymi z´asobn´ıkov´ymi automaty je
uzavˇren´a vzhledem k operaci dopl

Stáhnout celý tento materiál

Předchozí

1 2 3

Další

Vloženo: 25.04.2009

Velikost: 49,06 kB

Stáhnout celý tento materiál

Komentáře

Tento materiál neobsahuje žádné komentáře.