Prienik automatov, metoda skladania

BI-AAG
BI

asked 2014-11-16 13:16:50 +0100

Anonymous

updated 2014-11-16 13:37:50 +0100

Ahojte, chcel by som sa este spytat, aby som si bol isty v jednej veci. Mam ulohu napr.

Jazyky nad {a,b}. První jazyk obsahuje věty, kde počet 'a' je dělitelný třema. Druhý jazyk obsahuje věty, které obsahují 'aab'. Udělejte průnik automatů. (metoda skládání)

Nakreslim si obidva automaty a prepisem ich do tabulky. Potom tie dve tabulky prepisem do jednej podobnym sposobom ako pri determinizacii, to znamena, spojim vstupne stavy do jedneho, a doplnujem do tabulky kam sa to posuva. Ak vznikne novy stav dopisem. A aby bol stav vystupny, musia byt obidva vystupne stavy z povodnych automatov (napr. prvy automat mal vystupny stav A a druhy automat mal vystupny B, tak stav AB bude vystupny, no napr CB uz vystupny nebude.) Je to tak spravne? A este otazka na doplnok automatu, tie stavy, ktore nie su vystupne tak budu, a co s vystupnymi stavmi? Zmenia sa na vstupne? Dakujem velmi pekne.

edit retag flag offensive close delete

-1

answered 2014-11-16 16:59:36 +0100

Jan Rubín
265 ●9 ●17 ●24

K otázce koncových stavů:

Normálně z představy sjednocení a průniku... Když máš sjednocení množin, tak ti stačí, když aspoň v jedné ten prvek je. Stejně tak s koncovými stavy - aspoň jeden stav z těch koncových tam musí být. Analogicky s průnikem - musejí být oba.

Doplněk: První věc, co tě musí zajímat je, zda je automat úplně určený a deterministický. Jinak doplněk nemůžeš vůbec udělat. Pokud jsou tyto dvě podmínky splněny, pak doplněk uděláš tak, že prohodíš počáteční a koncové stavy a samozřejmě směr šipek. To je vše.

edit flag offensive delete publish link

Comments

Směr šipek? Proč proboha?

Radomír Polách ( 2014-12-01 02:34:05 +0100 )edit

3

answered 2014-11-16 18:07:12 +0100

Viktor Chlumský
765 ●14 ●24

Co se týče průniku, ano postup který popisujete je v pořádku.

Co se týče doplňku, zkuste se zamyslet nad tím, čeho chcete dosáhnout. Jde přece o to, aby odpověď automatu po přečtení řetězce byla opačná. Vzhledem k tomu, že odpovědí je to, zda se automat nachází v koncovém stavu, stačí vlastně všechny koncové stavy změnit na normální (nekoncové), a naopak.

Tato úvaha samozřejmě funguje jen pro deterministický automat, protože jinak je odpovědí spíše to, zda se může nacházet v koncovém stavu, a to se po provedení takovéhoto prohození nemusí změnit. Automat navíc musí být úplný, aby bylo jisté, že řetězec přečte celý, a nezavrhne jej předčasně (právě takové řetězce teď chceme naopak přijmout).

Takže automat musíte nejprve převést na úplný deterministický. Úplnost zajistíte přidáním "chybového" stavu, kam povedou všechny možnosti, pro které neexistují přechody, a ve kterém automat zůstává na jakýkoliv vstup. Poté můžete obrátit "koncovost" všech stavů.

edit flag offensive delete publish link

Prienik automatov, metoda skladania

2 Answers

Comments

Your answer

Question tools

Stats

Related questions