Matematické Fórum

silapo.72

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

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

Jookyn · 23. 03. 2011 22:53

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

claudia · 24. 03. 2011 01:06

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

silapo.72 · 24. 03. 2011 10:21

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

claudia · 24. 03. 2011 13:14

↑ 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$ ?

silapo.72 · 24. 03. 2011 14:54

↑ 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í.

Jookyn · 24. 03. 2011 17:10

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"

silapo.72 · 24. 03. 2011 17:39

↑ 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

Kondr · 24. 03. 2011 17:50

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

silapo.72 · 24. 03. 2011 18:19

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

Matematické Fórum

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

Bezkontextová gramatika

#2 23. 03. 2011 22:53

Re: Bezkontextová gramatika

#3 24. 03. 2011 01:06

Re: Bezkontextová gramatika

#4 24. 03. 2011 10:21

Re: Bezkontextová gramatika

#5 24. 03. 2011 13:14

Re: Bezkontextová gramatika

#6 24. 03. 2011 14:54

Re: Bezkontextová gramatika

#7 24. 03. 2011 17:10

Re: Bezkontextová gramatika

#8 24. 03. 2011 17:39

Re: Bezkontextová gramatika

#9 24. 03. 2011 17:50

Re: Bezkontextová gramatika

#10 24. 03. 2011 18:19

Re: Bezkontextová gramatika

Zápatí