Loading presentation...
Prezi is an interactive zooming presentation

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Formální jazyky

No description
by

Michal Černý

on 23 September 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Formální jazyky

Regularní jazyky
Nejejednodušší varianta jazyka
Všechny konečné jazyky jsou regulární
Ale regulární jsou také další jazyky
Bezkontextové jazyky
Chomského hierarchie
1956
Formální jazyky
Regulární gramatika
Jen pravidla:
A->wB
A->w
S->ε ... pokud S není na žádné pravé straně
Konečný automat
Formálně je konečný automat definován jako uspořádaná pětice ( S, Σ, σ, s, F), kde:
S je konečná neprázdná množina stavů.
Σ je konečná neprázdná množina vstupních symbolů, nazývaná abeceda.
σ je tzv. přechodová funkce (též přechodová tabulka), popisující pravidla přechodů mezi stavy. Může mít buď podobu S × Σ → S (deterministický automat), nebo S × {Σ ∪ ε} → P(S) (nedeterministický automat), viz níže.
s je počáteční stav, s ∈ S.
F je množina přijímajících stavů, F je podmnožinou S.
Co to je (formální) jazyk
Množina slov nad určitou abecedou, vytvořená určitou gramatikou
Každý nižší typ gramatiky obsahuje také všechny vyšší
Gramatika - předpis, jak má jazyk vypadat
Formální jazyk - je generován jasně definovanou gramatikou
Formát pravidel ovlivňuje vyjadřovací sílu jazyka
Přirozený jazyk - je hrou plnou "nepřístojností"
Formální jazyk může být definován různými způsoby, například:
slova generovaná nějakou formální gramatikou;
slova vyhovující nějakému regulárnímu výrazu;
slova akceptovaná nějakým automatem.
Základní pojmy:
Abeceda (terminální symboly)
Neterminální symboly
Přechodová funkce
Pravidlo gramatiky
Počáteční stav
Koncový stav
Prázdné slovo
Gramatika typu 0 - Turingův stroj
Gramatika typu 1 - lineárně označený TM
Gramatika typu 2 - zásobníkový automat
Gramatika typu 3 - konečný automat
Automat je ekvivalentní gramatice
prázdný jazyk Ø je regulární;
pro každé a z abecedy, jazyk { a } je regulární;
pokud A a B jsou regulární jazyky, jsou:
A ∪ B (sjednocení),
A • B (konkatenace),
a A* (iterace) také regulární.
žádné další jazyky regulární nejsou.
Regulární výrazy
Bezkontextová gramatika
Zásobníkový automat
Bezkontextové jazyky lze reprezentovat:

bezkontextovou gramatikou
zásobníkovým automatem
rozšířeným zásobníkovým automatem
Přechodová funkce:
(q, a, Z) -> (r, D)
Chomského normální forma: X->YZ|a
Greibachové normální forma: X->aB kde B je libovolný počet neterminálních symbolů
Rozhodnutelné problémy:
Prázdnost jazyka
Problém příslušnosti
Problém konečnosti jazyka
Nerozhodnutelné problémy:
Ekvivalence gramatik
Inkluse
Turingův stroj
Model výpočetního stroje, který je limitou výpočetních možností
Širší souvislosti
Podobně jako zásobníkový automat:
Je to uspořádaná šestice:
Množina vnitřních stavů
Abeceda symbolů
Počáteční stav
Prázdný symbol
Přechodová funkce umí jen pohyb hlavy po pásce do leva nebo do prava o jedno políčko

Čtení je obecně destruktivní, takže symbol se přečte a na jeho místo se něco zapíše
Každý algoritmus lze převést na TM
Literatura
:
ČERNÁ, Ivana, Mojmír KŘETÍNSKÝ a Antonín KUČERA. Formální jazyky a automaty I. Elportál, Brno: Masarykova univerzita, 2006. ISSN 1802-128X.
CHOMSKY, Noam. Three models for the description of language. Information Theory, IRE Transactions on, 1956, 2.3: 113-124.
SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997. xv, 396 s. ISBN 0-534-94728-X.
SATRAPA, Pavel. Regulární výrazy. 2000. Dostupné z: http://www.nti.tul.cz/~satrapa/docs/regvyr/regvyr.pdf
Full transcript