Matematické Fórum

JiMi · 02. 06. 2008 18:02 — Editoval JiMi (02. 06. 2008 21:01)

Zdravim , potreboval bych poradit s timto prikladem , nejak nevim si rady odkud zacit. Dostal jsem to resit jako projekt. Diky za kazdou pomoct.

Zadání :

Příklad 3:
Předpokládejme, že máme dánu nějakou bezkontextovou gramatiku G, jejíž každé pravidlo je
jednoho ze dvou následujících typů:
• Na pravé straně jsou dva neterminály (a žádné terminály), například X −> Y Z.
• Na pravé straně je pouze jeden terminál, například X −> a.
(Poznámka: O takové gramatice říkáme, že je v Chomského normální formě.)
Předpokládejme, že gramatika G obsahuje b neterminálů. Ukažte, že pokud v ní existuje
derivace nějakého slova, která má více než 2^b kroků, pak je jazyk L(G) nekonečný.

Kondr · 02. 06. 2008 18:57

Nemá tam být 2b ale 2^b. Viz gramatika
A->BB
B->CC
C->DD
D->a
(A je kořen,a terminál)
Ta popisuje jazyk obsahující pouze slovo aaaaaaaa, počet derivací je 1+2+4+8=15, přičemž má jen 4 neterminály.

Mějme konečný jazyk popsaný gramtikou, která je v Chomského n.f. a má b neterminálů. Protože je konečný, nemůže gramatika obsahovat rekurzi. Neterminály lze tedy očíslovat od 0 do b-1 tak, že derivacemi z neterminálu i nikdy nedostaneme řetězec, který by obsahoval neterminál s číslem i nebo nižším. Kořen gramatiky má číslo 0. Dále terminálu číslo i přiřaďme hodnotu $\left(\frac{1}{2}\right)^i$ , terminálům hodnotu
$\left(\frac{1}{2}\right)^{b-1}$ . Lze pak definovat hodnotu větné formy jako součet hodnot všech jejích prvků. Např. v uvedené gramatice
jsou hodnoty neterminálů A,B,C,D postupně 1, 1/2, 1/4, 1/8, hodnota neterminálu a je 1/8. Forma $BCC$ má hodnotu 1/2+1/4+1/4=1.
Nahrazení neterminálu terminálem zřejmě hodnotu formy nezvýší. Nahrazujeme li terminál o hodnotě $\left(\frac{1}{2}\right)^i$ dvěma neterminály, může každý z nich mít (kvůli neexistenci rekurse) hodnotu nejvýše $\left(\frac{1}{2}\right)^{i+1}$ , ani takováto náhrada hodnotu větné formy nezvýší. Protože kořen má hodnotu 1, musí mít i výsledné slovo hodnotu nejvýše 1, může se tedy skládat nejvýše z $2^{b-1}$ neterminálů. Pro gramatiku v Chomského normální formě platí, že počet derivací je dvojnásobkem počtu znaků výsledného slova sníženým o 1 (ponecháno čtenáři k důkazu). Proto každé slovo našeho jazyka lze získat nejvýše $2^b-1$ derivacemi.

Pokud je k získání nějakého slova potřeba derivací více, nemůže být jazyk konečný.

JiMi · 02. 06. 2008 20:58

jo sry .. sem si nevsiml ... ma tam byt 2^b

lukon · 23. 06. 2008 09:56

Zdravím.

Mám podobný a stejně nepřekonatelný problém. Dostal jsem projekt, nad kterým vážně tápu (už dlouho).
Uvítám jakoukoli pomoc!

Příklad 41

Předpokladejme, že mame danu nějakou bezkontextovou gramatiku G, jejiž
každe pravidlo je jednoho ze dvou nasledujicich typů:

• Na prave straně jsou dva neterminaly (a žadne terminaly), napřiklad X → Y Z.
• Na prave straně je pouze jeden terminal, napřiklad X → a.

(Poznámka: O takove gramatice řikame, že je v Chomskeho normalni formě.)

Ukažte, že pro libovolne slovo w ∈ L(G) delky n, kde n ≥ 1, plati, že jakakoliv derivace
tohoto slova v gramatice G ma pravě 2n − 1 kroků.

Matematické Fórum

#1 02. 06. 2008 18:02 — Editoval JiMi (02. 06. 2008 21:01)

Bezkontektová gramatika

#2 02. 06. 2008 18:57

Re: Bezkontektová gramatika

#3 02. 06. 2008 20:58

Re: Bezkontektová gramatika

#4 23. 06. 2008 09:56

Re: Bezkontektová gramatika

Zápatí