Matematické Fórum

Zdenek01

Prosím uměl by to někdo vyřešit:

Oznacme bin(x) slovo nad abecedou {0, 1}, ktere je binarnim zapisem prirozeneho cisla x náleži N (N je množina přirozených čísel) bez vedoucich nul, takže napriklad bin(13) = 1101. Jedinou vyjimkou je cislo 0, kde definujeme, že bin(0) = 0.
Navrhnete bezkontextovou gramatiku generujici nasledujici jazyk L nad abecedou {0, 1, #}:
L = { bin(x)^R # bin(x + 1) | x náleží N}

Díky za pomoc

Zdenek01 · 02. 05. 2010 21:59

Prosím Vás potřeboval bych trochu poradit s tímto příkladem. Děkuji

Kondr · 04. 05. 2010 09:41

Když je bin(x) tvaru w0, je bin(x+1) tvaru w1.
Když je bin(x)=0, je bin(x+1)=1.
Když je bin(x) tvaru 11....1, je bin(x+1) tvaru 100...0.
Když je bin(x) tvaru w011....1, je bin(x+1) tvaru w100...0.

Slova v jazyce jsou proto jednoho ze čtyř typů
0w^R#w1
0#1
11...1#100...0
11...10w^R#w100...0

Neterminál A pro gnerování w^R#w najdeme snadno (to jistě bude ve skriptech, která tu stále dokola odkazuji) a pak jen vyrobíme ten neterminály

B -> 0A1
C -> 1B0 | 1C0
D -> #1 | 1D0
S -> 0#1| B | C | D

Píšu to dost narychlo, tak doufám, že tam není chyba a že je hlavně jasná myšlenka.

Zdenek01

↑ Kondr: Bude ten neterminál A vypadat nějak takto?

A -> # | 0A0 | 1A1

Jinak ten neterminál D tam v podstatě ani nemusí být, ale za předpokladu když #1 strčím do neterminálu C. Doufám, že se nepletu

Kondr · 05. 05. 2010 21:01

↑ Zdenek01: Ano, to je přesně ono. Je u toho zbytku vidět, jak se na to došlo?

Zdenek01 · 05. 05. 2010 22:29

↑ Kondr: Ano díky moc, konečně tomu začínám rozumět. Diky moc za pomoc.

Jinak ten neterminál D už je tam celkem zbytečný stačí toto #1 vložit do neterminálu C a vyjde to úplně nastejno. Doufám, že se nepletu?

Kondr · 06. 05. 2010 01:21

↑ Zdenek01: Opravdu, neterminály C a D se dají takto spojit.

Matematické Fórum

#1 27. 04. 2010 18:00 — Editoval Zdenek01 (28. 04. 2010 17:31)

bezkontextová gramatika

#2 02. 05. 2010 21:59

Re: bezkontextová gramatika

#3 04. 05. 2010 09:41

Re: bezkontextová gramatika

#4 05. 05. 2010 20:41 — Editoval Zdenek01 (05. 05. 2010 22:24)

Re: bezkontextová gramatika

#5 05. 05. 2010 21:01

Re: bezkontextová gramatika

#6 05. 05. 2010 22:29

Re: bezkontextová gramatika

#7 06. 05. 2010 01:21

Re: bezkontextová gramatika

Zápatí