Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 23. 03. 2011 21:47 — Editoval silapo.72 (23. 03. 2011 21:47)

silapo.72
Zelenáč
Příspěvky: 17
Reputace:   
 

Bezkontextová gramatika

Dobrý večer, potřeboval bych poradit s příkladem:


http://www.sdilej.eu/pics/031c48e429693d021bdae3e0306bd8c0.bmp

L1 ?
L2  by mohlo být:
S2->BabaB|BbbB
B-> epsilon|Ba|Bb

Celkově pak:
  S->S1 a S2
Dále pak pravidla obou gramatik

Offline

  • (téma jako vyřešené označil(a) jelena)

#2 23. 03. 2011 22:53

Jookyn
Místo: Mar. Lázně / Praha
Příspěvky: 143
Reputace:   11 
 

Re: Bezkontextová gramatika

L1: S -> epsilon|aaSb
L2 mi připadá OK

Offline

 

#3 24. 03. 2011 01:06

claudia
Richard P. Feynman
Příspěvky: 478
Reputace:   41 
 

Re: Bezkontextová gramatika

U S2 mi přijde, že navrhnutá pravidla generují jazyk "...obsahuje podslova 'bb' NEBO 'aba'..." namísto A, jak je zadáno. Navrhuji modifikaci: S2->BabaBbbB | BbbBabaB


Pište prosím své dotazy srozumitelně a v TeXu (Detexify). Píšete je jen jednou, ale my je čteme mnohokrát. Čím méně času strávím luštěním vaší otázky, tím více mi zbyde na její zodpovězení.

Offline

 

#4 24. 03. 2011 10:21

silapo.72
Zelenáč
Příspěvky: 17
Reputace:   
 

Re: Bezkontextová gramatika

K toku L2 souhlasím s modifikací S2->BabaBbbB

U toho L1 si nejsem jisty s tím S -> epsilon|aaSb. Mohl by mě to někdo trochu popsat? Potřeboval bych to pochopit.
Ty mocniny mě tam matou.
Dík

Offline

 

#5 24. 03. 2011 13:14

claudia
Richard P. Feynman
Příspěvky: 478
Reputace:   41 
 

Re: Bezkontextová gramatika

↑ silapo.72:

Pokud bys použil pouze pravidlo "S2->BabaBbbB", jak vygeneruješ slovo "bbaba", které do jazyka patří?

U toho L1 tedy nerozumíš tomu pravidlu, nebo nevíš, co znamená třeba $a^2$?


Pište prosím své dotazy srozumitelně a v TeXu (Detexify). Píšete je jen jednou, ale my je čteme mnohokrát. Čím méně času strávím luštěním vaší otázky, tím více mi zbyde na její zodpovězení.

Offline

 

#6 24. 03. 2011 14:54

silapo.72
Zelenáč
Příspěvky: 17
Reputace:   
 

Re: Bezkontextová gramatika

↑ claudia:
U L2  jsem myslel souhlas jen s  úpravou prví části.
Celá gramatika pro L2 by byla :

S2->BabaBbbB
B-> epsilon|Ba|Bb

U L1 nechápu  jak vyjádřím to $a^2$ , celkově ty mocniny v terminálech "a,b".
Prostě nevím jak vyjádřit v gramatice ty mocniny, když je to jen terminál a ne číslo.
A také se chci zeptat tím "n=2m" je myšleno, že každý exponent (mocnitel) nad terminálem "a" má dvakrát větší hodnotu než nad "b"?

Ale z gramatiky, která tu byla uvedena tj. S -> epsilon|aaSb, vyplývá, že terminálů "a" je dvakrát víc než "b".
To mě k těm mocninám nějak nesedí.

Offline

 

#7 24. 03. 2011 17:10

Jookyn
Místo: Mar. Lázně / Praha
Příspěvky: 143
Reputace:   11 
 

Re: Bezkontextová gramatika

Mocniny v gramatikách znamenají počet po sobě jdoucích terminálů, tzn $a^5$ znamená aaaaa

A za chybu, že jsem schválil L2 se omlouvam, nevšimnul jsem si "a"

Offline

 

#8 24. 03. 2011 17:39

silapo.72
Zelenáč
Příspěvky: 17
Reputace:   
 

Re: Bezkontextová gramatika

↑ Jookyn:
Díky za vysvětlení. Takže to shrnu. Celková gramatika L1 U L2 by měla vypadat asi takto:

S  -> S1 + S2
S1 -> epsilon|aaSb
S2 -> B abaBbbB
B  -> epsilon|Ba|Bb

Offline

 

#9 24. 03. 2011 17:50

Kondr
Veterán
Místo: Linz, Österreich
Příspěvky: 4246
Škola: FI MU 2013
Pozice: Vývojář, JKU
Reputace:   38 
 

Re: Bezkontextová gramatika

↑ silapo.72:
mělo by být
S2->BabaBbbB | BbbBabaB
a
S-> S1 | S2 (nejde o chybu, pouze o nekonzistentní zápis)


BRKOS - matematický korespondenční seminář pro střední školy

Offline

 

#10 24. 03. 2011 18:19

silapo.72
Zelenáč
Příspěvky: 17
Reputace:   
 

Re: Bezkontextová gramatika

↑ Kondr:
Díky za doplnění.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson