Ask Your Question
0

Prienik automatov, metoda skladania

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

anonymous user

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

2 Answers

Sort by » oldest newest most voted
3

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

Viktor Chlumský gravatar image

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 more
-1

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

Jan Rubín gravatar image

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 more

Comments

Směr šipek? Proč proboha?

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

Your answer

Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!

Add answer

[hide preview]

Question tools

Follow
1 follower

Stats

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

Seen: 615 times

Last updated: Nov 16 '14