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 25. 03. 2011 22:45

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

Návrh bezkontextové gramatiky

Zdravím,
potřeboval bych poradit se sestavením bezkontextové gramatiky.

http://www.sdilej.eu/pics/b95bfebdbf26e3b3b63ae0782c47114e.bmp

L1:  ? nedaří se mě zformulovat pravidlo aby se za „abb“ nebo před „ bba“ neoběvil terminál „a“
L2:  A-> AbAbA|Aa|epsilon

L:  S-> AB 
Jazyk L bude zřetězením L1 a L2 . Pod ním budou následovat pravidla obou dvou jazyků.

Děkuji.

Offline

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

#2 26. 03. 2011 00:21 — Editoval claudia (26. 03. 2011 00:21)

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

Re: Návrh bezkontextové gramatiky

"neobsahuje slovo abba" je ekvivalentní podmínce, že mezi dvěma znaky "a" nesmí být právě dva znaky "b", může tam být 0, 1 nebo 3 a více. Takže bych nejprve rozmístila potřebný počet "a" a pak mezi každá dvě umožnila dát buď nic nebo jedno "b" nebo 3 "b" s možností přidání dalších "b". Na začátku a na konci slova (před prvním a za posledním "a") může být libovolný počet znaků "b".

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

 

#3 26. 03. 2011 09:22

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

Re: Návrh bezkontextové gramatiky

↑ claudia:

Zkusil jsem to dát dohromady podle toho popisu, snad to bude sedět.
Dole je celkový výsledek. To L2 jsem také přepsal.


L1 : S1-> a|A|B|AaAaA
        A-> epsilon|b|bAbAb
        B-> bb

L2:  S2 -> epsilon|S2a| S2bS2bS2 
       

L: S->S1S2

    S1-> a|A|B|AaAaA
    A-> epsilon|b|bAbAb
    B-> bb

    S2 -> epsilon|S2a|S2bS2bS2

Offline

 

#4 26. 03. 2011 09:28

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

Re: Návrh bezkontextové gramatiky

Tak to si nejsem jistá. Jak bys vygeneroval třeba "bbbbb"?

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

 

#5 26. 03. 2011 09:37

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

Re: Návrh bezkontextové gramatiky

↑ claudia:

Podle mě takto :

Z počátečního neterminálu S1 odvodím neterminál A, z A odvodím  bAbAb a  z neterminálů A co jsou mezi třemi terminály  "b" odvodím  dva terminály "b".

Offline

 

#6 26. 03. 2011 09:42

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

Re: Návrh bezkontextové gramatiky

OK, omlouvám se, špatně jsem si to přečetla. Jak bys vygeneroval "aaaaa"? :-)

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

 

#7 26. 03. 2011 09:51

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

Re: Návrh bezkontextové gramatiky

↑ claudia:

Tak teďka jsi mě dostala zase ty :-) To jsem přehlédl zase já.
Musím upravit ten L1.
Níže je výsledek. Z toho už by to mělo být jasné.

L1 : S1-> A|B|AaAaA
        A-> epsilona|a|b|bAbAb
        B-> bb

Offline

 

#8 26. 03. 2011 09:55 — Editoval claudia (26. 03. 2011 13:04)

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

Re: Návrh bezkontextové gramatiky

Zrovna jasné mi to není ani trochu. Nevidím v tom žádnou logiku. Pokud tam nějaká je, můžeš klidně přidat slovní komentář :-) Co slovo "bba"? :-)

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

 

#9 26. 03. 2011 10:38

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

Re: Návrh bezkontextové gramatiky

↑ claudia:
No vidím, že dostávám pořádně na zadek :-)
Ale lepší tady než u zkoušky.
Takže zase uprava L1

L1 : S1-> A|B|Abb|bbA|AaBaA
        A-> epsilon|a|b|AaA
        B-> bAbAb

To "aaaaa" dostanu takto:

Z S1 vygeneruji A z něho  AaA  dosadím za pravé A  podslovo  AaA  dostanu  AaAaA   a pak  za A doplním  terminály "a"

"bba" dostanu následujícím postupem:

Z S1 vygeneruji bbA pak A nahradím terminálem "a"

Nějak se v tom zamotávám :-)

Offline

 

#10 26. 03. 2011 12:54 — Editoval claudia (26. 03. 2011 12:55)

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

Re: Návrh bezkontextové gramatiky

↑ silapo.72:

To je přesně ten problém. Lehčí jazyky jdou generovat metodou pokus-omyl, ale u složitějších je to ... složitější. Zvláště, kdybych teď pravila "dokaž, že to generuje právě to, co má".

Je asi lepší přístup mít nějakou počáteční myšlenku, která se dá do těch pravidel převést snadno, přitom je snadné nahlédnout, že je správná. Třeba to, co jsem psala výše - nejdříve vygenerovat všechna a, pak na začátek a na konec povolit libovoný počet b, doprostřed jen 0, 1 nebo 3+.

Není v mých silách vyřešit všechny tvé příklady, ale jednou to tedy zkusím ukázat:

$<L1> &::= <zacatek>\ <konec>\\ <zacatek> &::= <okraj>\\ <konec> &::= <stred> \mathbf{"a"} <konec> | <okraj>\\ <okraj> &::= <b*>\\ <stred> &::= \epsilon\ |\ \mathbf{"b"}\ |\ \mathbf{"bbb"} <b*>\\ <b*> &::= \epsilon\ |\ \mathbf{"b"} <b*> $

Rozhodně to není nejstručnější způsob, jak to zapsat, ale chtěla jsem, aby k tomu nebyl třeba další komentář :-) Až si to promyslíš, můžeš sjednotit začátek, okraj a b*, protože mají zjevně stejný význam.

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

 

#11 26. 03. 2011 17:53

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

Re: Návrh bezkontextové gramatiky

↑ claudia:

Díky moc za ochotu a čas, který tím ztrácíš.
Jde mě hlavně o to najít nějaký systém při generování složitějších jazyků abych to nezkoušel stylem pokus omyl, jak píšeš.
Sestavil jsem to podle toho návodu a snažil se srozumitelně popsat postup.

A-začátek
B-konec
C-okraj
D-střed
E-b*

S-> AB
A-> C
B->DaB|C
C->E
D->epsilon|b|bbbE
E->epsilon|bE

Pak jsem sjednotil začátek , okraj a b*  tj. (A,C,E) do A.
Poté jsem přejmenoval D na C.
A vyšlo mi pro L1:

S->AB
A->epsilon|bA
B->CaB|A
C->epsilon|b|bbbA

Offline

 

#12 26. 03. 2011 19:46

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

Re: Návrh bezkontextové gramatiky

Ve skutečnosti to nejspíše z toho "mého tvaru" přepisovat nemusíš, tak se naopak bezkontextové gramatiky tradičně zapisují:

http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form

Systém sama žádný nemám. Možná existuje nějaký univerzální algoritmus. Ale pravděpodobně nebude dávat elegantní výsledky. Nejspíše to patří mezi úlohy, kde je třeba zapojit fantazii :-)

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

 

#13 26. 03. 2011 20:21

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

Re: Návrh bezkontextové gramatiky

↑ claudia:
Ještě jednou díky za pomoc a za zajímavý odkaz ;)

Offline

 

 

Stránky: 1

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson