Matematické Fórum

fatality · 04. 05. 2013 18:42

Při převodu bezkontextové gramatiky do Chomského normální formy
se po odstranění pravidel typu A → $\varepsilon$ provádí krok, který odstraňuje pravidla typu X → Y
(neterminál se přepisuje na neterminál). (Pak tedy dostaneme jen pravidla typu A → $\alpha$
kde je terminál nebo | $\alpha$ | ≥ 2, přičemž generovaný jazyk se nezměnil.)
Na vhodném příkladu ilustrujte algoritmus odstraňující ona pravidla X → Y a ukažte jeho korektnost.

Převod do Chomského normální formy zvládám, jen mě nenapadá jak dokázat korektnost. Potřeboval bych náznak jak se u takovéhoto typu příkladu tato korektnost dokazuje.

Děkuji za odpověď.

JohnPeca18 · 05. 05. 2013 12:23

Tak ja bych to dokazoval vetu, bezkontextova gramatika $G$ generuje prave ty slova, ktere generuje gramatika $G$ po prevedeni na Chomskeho normalni formu, oznacme treba $\bar{G}$ . Dokazuji 2 implikace. Kazde slovo ktere generuje $G$ , generuje taky $\bar{G}$ . Dokazu to tak, ze pravidlo ktere jsem pri prevodu odstranil z ${G}$ nahradim prislusnou sekvenci pravidel z $\bar{G}$ .
Opacnou implikaci bych dokazoval nejak sporem. Tam bys spis potreboval nahrazovat skupiny zpatky. No nevim jestli to nejak pomohlo. . kdyz tak napis v cem konkretne je problem, treba se na to prijde.

Matematické Fórum

#1 04. 05. 2013 18:42

Bezkontextové gramatiky - Chomského normální forma korektnost

#2 05. 05. 2013 12:23

Re: Bezkontextové gramatiky - Chomského normální forma korektnost

Zápatí