#1 30. 11. 2013 03:18
Gramatiky
Dobrý den,
mám následující zadání:
Jsou dány tyto gramatiky:
G1:
S -> aaA | bB | e
A -> aaA |bbB | a
B -> baA |abB | b
G2:
S -> baA | abB | B
A -> B | bB | e
B -> babA | abb | e
dále je za úkol sestrojit nedeterministický automat A takový, že L(A) = L(G1) . L(G2)^R
Problém mám hned na začátku. chci napsat automaty akceptující G1 a reverzní G2. Ale nevím jak tyto automaty sestrojit. Nejsem si jist např. u pravidla S -> a. Mám tedy automat nejdříve gramatiku převést do regulárního tvaru? Opravu si zde nevím rady.
Budu vděčný za každý komentář.
Děkuji
Offline
#2 02. 12. 2013 12:00
- vojta_vorel
- Příspěvky: 70
- Škola: MFF UK
- Pozice: student
- Reputace: 5
Re: Gramatiky
↑ zotac: Na sestrojení nedeterministického zásobníkového automatu pro jazyk daný bezkontextovou gramatikou existuje přímočarý mechanický postup, viz třeba http://ktiml.mff.cuni.cz/~bartak/automaty/ .
Až si ujasníš, jak to funguje, tak je ovšem potřeba vymyslet tu reverzi a to spojení jazyků.
Vojta
Offline
#3 04. 12. 2013 19:42
Re: Gramatiky
↑ vojta_vorel: Dobrý den, děkuji z Váš příspěvek. Příklad se mi již podařlo vyřešit a to následovně.
1) Gramatiky G1 a G2 jsem převedl do regulárního tvaru.
2) Díky kroku jedna již bylo možné sestavit automaty
3) Automat ke G2 jsem udělal reverzní (přehození počátečních a koncových stavů a přehození směru hran)
4) G1 a G2 reverzní jsem spojil e-hranami (všechny koncové stavy G1 jsem spojil e-hranami s všemi počátečními stavy G2 reverzní)
Offline
#4 05. 12. 2013 08:41
- vojta_vorel
- Příspěvky: 70
- Škola: MFF UK
- Pozice: student
- Reputace: 5
Re: Gramatiky
Ahoj
Omlouvám se, nevšiml jsem si, že jsou tvoje gramatiky regulární a že tedy půjde udělat konečný automat. Já jsem mluvil o postupu, který funguje i pro divočejší gramatiky ale vytváří se divočejší automat. Moje chyba.
To co píšeš rozhodně zní rozumně, souhlasím.
Takže vlastně dobře, že jsem ti nepomoh a mohl sis na to přijít sám, že :)
Vojta
Offline
#5 05. 12. 2013 19:14
Re: Gramatiky
↑ vojta_vorel: Dobrý den, rozhodně se neomlouvejte, slaidy od Vás mě dovedly ke správnému řešení. Takže ještě jednou děkuji :)
Offline