Biautomaty
Tato bakalářská práce se zabývá tematikou biautomatů. Navazujeme na deterministické biautomaty a zavádíme jejich nedeterministická rozšíření,jejichž nejobecnější varianta rozpoznává lineární jazyky. Nedeterministické biautomaty poté využíváme k důkazům tvrzení o lineárních jazycích, jako je např. pu...
Uloženo v:
| Hlavní autor: | |
|---|---|
| Další autoři: | |
| Typ dokumentu: | VŠ práce nebo rukopis |
| Jazyk: | Čeština |
| Vydáno: |
2014
|
| Témata: | |
| On-line přístup: | http://is.muni.cz/th/103497/prif_b/ |
| Shrnutí: | Tato bakalářská práce se zabývá tematikou biautomatů. Navazujeme na deterministické biautomaty a zavádíme jejich nedeterministická rozšíření,jejichž nejobecnější varianta rozpoznává lineární jazyky. Nedeterministické biautomaty poté využíváme k důkazům tvrzení o lineárních jazycích, jako je např. pumping lemma pro lineární jazyky nebo tvrzení o uzavřenosti a neuzavřenosti lineárních jazyků na mnohé operace. Nakonec srovnáváme biautomaty s jinými již zavedenými modely a dokazujeme, že nelze algoritmicky rozhodnout, zda nedeterministický biautomat rozpoznává regulární jazyk. In this thesis we study biautomata. We extend deterministic biautomata with nondeterminism in several ways. The most general variant then recognizes linear languages. Further, we use non-deterministic biautomata to prove results on linear languages such as the pumping lemma and closure properties of linear languages. Finally, we compare biautomata to existing models and prove that the problem whether a non-deterministic biautomaton recognizes a regular language is undecidable. |
|---|---|
| Popis jednotky: | Vedoucí práce: Ondřej Klíma |
| Fyzický popis: | 47 l. |