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

Stránky: 1

 

#1 22. 06. 2012 15:46

tascoa
Příspěvky: 46
Reputace:   0 
 

bezkontextova gramatika 1

Zdravim, mohl byste mi nekdo poradit jak vygenerovat bezkontextovou gramatiku z nasledujiciho jazyka:

$\{w\in \{a,b\}*| |w|_{a}>0 \wedge  \text{w zacina a konci stejnym symbolem}\}$

Existuje nejaky postup, jak zacit? Ja bych si nejdrive vypsal par slov ze zacatku, ktere jazyk vygeneruje, napr. a, aa, aba, bab, aaa apod.

Potom zacnu:

S -> aAa
A -> $\varepsilon $ | a | b

a tim koncim :(

Offline

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

#2 22. 06. 2012 17:53

Mr.Pinker
Příspěvky: 542
Reputace:   12 
 

Re: bezkontextova gramatika 1

a co takhle to generovat takto

S -> aAa

S -> bAb

A -> aA

A -> Aa

A -> bA

A -> a

A -> b

Offline

 

#3 22. 06. 2012 22:36

tascoa
Příspěvky: 46
Reputace:   0 
 

Re: bezkontextova gramatika 1

mohu si dovolit malou analyzu?

prvni dva radky resi podminku, kdy slovo zacina a konci stejnym symbolem?

zbyvajici radky 'pouze' resi zbytek pripadu, ktere mohou nastat?

nechybi potom tedy jeste:
A -> Ab

?

Offline

 

#4 22. 06. 2012 23:46

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

Re: bezkontextova gramatika 1

Ja bych to resil nejak takhle:

S -> aBa
S -> bAb
A -> aB
A -> bA
B -> lambda
B -> aB
B -> bB

Prvni dva radky resi, aby to zacinalo a koncilo stejnym pismenem. Dokud tam neni zadne a, tak to zustava v A, jakmile je tam vlozeno nejake a, tak se prejde do B a tam uz se davaji libovolne terminaly...

↑ tascoa:
Ne A -> Ab,tam nechybi, staci A -> bA. Naopak je ale zbytecne aby tam bylo A -> aA i A -> Aa, staci jedno, nic navic ta druha vec negeneruje a navic to dela gramatiku viceznacnou. Ale ta gramatika generuje i slovo bbbb, coz neni slovo daneho jazyka a naopak treba negeneruje aaa, coz je soucasti jazyka, takze mi neprijde jako odpovidajici danemu zadani...

Offline

 

#5 23. 06. 2012 10:19

Mr.Pinker
Příspěvky: 542
Reputace:   12 
 

Re: bezkontextova gramatika 1

jakto že bbb není součástí jazyka ? .... jen tak mimochodem to jedno je podmínka že četnost a musí být větší jak nula ?

Offline

 

#6 23. 06. 2012 10:26

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

Re: bezkontextova gramatika 1

↑ Mr.Pinker:
Ja to tak pochopil teda...

Offline

 

#7 24. 06. 2012 09:04

tascoa
Příspěvky: 46
Reputace:   0 
 

Re: bezkontextova gramatika 1

↑ Mr.Pinker: ja to take chapu tak, ze cetnost znaku a je vetsi nez nula. slovo bbb by tam tedy patrit nemelo...

Offline

 

#8 24. 06. 2012 09:48

tascoa
Příspěvky: 46
Reputace:   0 
 

Re: bezkontextova gramatika 1

jen pro kontrolu, jestli tomu alespon trochu rozumim - pro jazyk L vygeneruj bezkontextovou gramatiku

$L=\{a^{n}b^{n}|n\ge 0\}$

muj vysledek:

S -> aSb
S -> ab

Je tento priklad spravne?

Offline

 

#9 24. 06. 2012 11:28

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

Re: bezkontextova gramatika 1

↑ tascoa: Ano

Offline

 

#10 24. 06. 2012 16:51

tascoa
Příspěvky: 46
Reputace:   0 
 

Re: bezkontextova gramatika 1

↑ Jookyn: Kdyz jeste k tomuto jazyku pridam podminku, ze vygenerovane slovo musi odsahovat podslovo 'bb', mohla by vysledna gramatika vypadat nasledovne:

S -> BbbB | aSb
B -> epsilon | ab

?

Offline

 

#11 24. 06. 2012 17:35 — Editoval Jookyn (24. 06. 2012 17:36)

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

Re: bezkontextova gramatika 1

↑ tascoa: To bych nerekl, protoze takhle to generuje i slova "abbab" nebo "ab", ktera zrejme nejsou z daneho jazyka.

Tady bych se na to podival cca takhle. Pokud tam musi byt podslovo bb, pak tam musi byt minimalne podslovo aabb, aby platila rovnost poctu znaku a,b. A do jeho stredu pak muzes pridavat libovolne "ab".

Jinak jeste ted koukam, ze v predchozim prispevku jsem odsouhlasil gramatiku, ktera je spatne, protoze to negeneruje vsechna slova jazyka. Je potreba tam pridat jeste jedno pravidlo, jako cviceni necham jeho nalezeni, ale souvisi to s podminkou $n \ge 0$, ted to plati pouze pro $n \ge 2$, coz je paradoxne presne jazyk na ktery mirila posledni otazka.

Offline

 

#12 24. 06. 2012 18:00

tascoa
Příspěvky: 46
Reputace:   0 
 

Re: bezkontextova gramatika 1

↑ Jookyn:

Pro tu gramatiku bez podslova 'bb' muze byt takto:

S -> epsilon | ab | aSb

?

Pro gramatiku s podslovem 'bb':

muze gramatika generovat i slova abba, aabb, bbaa? Ta podminka, ze kdyz je nutnost obsahovat podslovo 'bb' zarucuje, ze automaticky musi kvuli podmince $n \ge 0$ obsahovat podslovo aabb se mi nezda.

Offline

 

#13 24. 06. 2012 18:20

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

Re: bezkontextova gramatika 1

↑ tascoa:
jj, je to tak, dokonce to jde i bez S -> ab, pokud je tam to pravidlo S -> epsilon.

S podslovem bb:

Tak pokud k jazyku $L=\{a^{n}b^{n}|n\ge 0\}$ pridame nutnost aby to obsahovalo bb, tak porad musi platit, ze prvnich n znaku jsou "a" a potom je n znaku "b", takze do toho mi abba a bbaa nepasuje... Takze ona z toho ta podminka na podslovo "bb" udela prakticky jazyk $L=\{a^{n}b^{n}|n\ge 2\}$

Offline

 

#14 24. 06. 2012 18:32

tascoa
Příspěvky: 46
Reputace:   0 
 

Re: bezkontextova gramatika 1

↑ Jookyn:

Pro gramatiku s podslovem 'bb' bude vysledek:

S -> AaabbB
A -> epsilon | a
B -> epsilon | b

?

Offline

 

#15 24. 06. 2012 22:11

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

Re: bezkontextova gramatika 1

↑ tascoa:
No, tohle nefunguje, protoze to jednak neudrzi stejne pocty "a" a "b", ale hlavne to temer nic negeneruje (mozna jsi chtel napsat ty pravidla A -> epsilon | aA), takhle se hned prepise A na terminal a uz s tim nejde nic delat. Takze tahle gramatika generuje jen 3 slova: aabb, aaabb, aabbb a z toho 2 ani nejsou soucasti jazyka.

Je potreba tam generovat najednou "ab", aby se to "nerozhodilo". A to je mozne pridavat jedine do stredu toho vznikajiciho slova. Takze treba takhle:

S -> aaAbb
A -> epsilon | aAb

Offline

 

#16 24. 06. 2012 22:41

tascoa
Příspěvky: 46
Reputace:   0 
 

Re: bezkontextova gramatika 1

↑ Jookyn:

to A v prvnim radku S -> aaAbb se pri generovani muze opakovat vicekrat?

Offline

 

#17 24. 06. 2012 23:02

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

Re: bezkontextova gramatika 1

Asi uplne nevim, jak to myslis... Ale mozna mas trosku nejasnosti, jak to generovani probiha. Probiha to po krocich, tady zhruba takto:

Mame pocatecni neterminal S
Podle jedineho pravidla se prepise na aaAbb
-- Tady zacina nedeterminismus - pro A existuji 2 pravidla, v kazdem kroku si gramatika "muze vybrat" jake pouzije
Pouzitim A -> aAb ziskame aaaAbbb
Pouzitim A -> aAb ziskame aaaaAbbbb
Pouzitim A -> epsilon ziskame aaaabbbb a konci odvozovani.

Pokud mame na vyber, ktery neterminal (slovo ze ktereho odvozujeme je treba tvaru AabB) se bude prepisovat, tak si gramatika "opet muze vybrat".

Pokud byla myslena otazka, jestli to pravidlo muze byt jako S -> aaAAbb, tak odpoved zni ne, zkus najit, jake slovo ktere neni soucasti jazyka to muze vygenerovat.

Offline

 

#18 25. 06. 2012 21:38

tascoa
Příspěvky: 46
Reputace:   0 
 

Re: bezkontextova gramatika 1

↑ Jookyn:

mohlo by to vygenerovat slovo aaababbb, ktere neni soucasti jazyka.

je to tak?

Offline

 

#19 25. 06. 2012 22:03

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

Re: bezkontextova gramatika 1

↑ tascoa:
jj, presne.

Offline

 

#20 25. 06. 2012 22:29

tascoa
Příspěvky: 46
Reputace:   0 
 

Re: bezkontextova gramatika 1

↑ Jookyn:

diky za pomoc, snad uz tomu zacinam rozumnet :)

Offline

 

 

Stránky: 1

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson