Teoretické základy informatiky

Alan Turing (1912-1954) “the father of modern computer science”
Alan Turing (right) at the console of the Manchester computer
The Enigma cipher machine
Alan Turing
ZDROJE:
http://www.turing.org.uk/turing/
http://en.wikipedia.org/wiki/Alan_Turing
Replica of a bombe machine
1936 práca "On Computable Numbers with an application to the Entscheidungsproblem" -model abstraktných výpočtových strojov pre rôzne výpočty, používal unárnu číselnu sústavu, pripočítanie zreťazením, dokáže realizovať akýkoľvek algoritmus
1940 Turing-Welchman Bombe, 1939-1942 práca na dešifrovacom stroji pre Enigmu počas 2. svetovej vojny
1950 Computing Machinery and Intelligence
Turingov test v umelej inteligencii, ako dosiahnuť, aby stroj myslel ako človek

Turingov stroj – neformálny popis
Výpočtový model reprezentovaný Turingovým strojom:
riadiaca jednotka,
čítacia/zapisovacia hlava
nekonečná vstupná páska.

Turingov stroj
Turingov stroj = Turing machine
TS, TM
Hlava – číta aj prepisuje
Pohyb hlavy – vpravo, stoj, vľavo
Páska – nekonečná, za hranicami slova sú symboly „blank“ - B
RJ

Definícia - Turingov Stroj
≤

TS: Konfigurácia, krok výpočtu

Riešený príklad TM pre L1={anbncn | nЄN+}

Techniky pri konštrukcii TM
Viacnásobné stopy
Zapamätanie si symbolov v stave
Označovanie symbolov
Podprogramy - simulovanie

Príklady
L2={w1i#1i#1iwR | wЄ{a,b}*, iЄN+}
L3={wcw | wЄ{a,b}*} Є LCS
L4={wwR | wЄ{a,b}+} - NPDA, DTM

Trieda jazykov rozpoznávaná TS

Uzáverové vlastnosti triedy LRE

Chomského hierarchia jazykov
LRE Trieda rekurzívne vyčísliteľných jazykov, generovaných frázovou gramatikou (Turingov Stroj)
LCS Trieda kontextových jazykov, generovaných kontextovou gramatikou (Lineárne ohraničený Automat)
LCF Trieda bezkontextových jazykov, generovaných bezkontextovou gramatikou (Zásobníkový Automat)
R Trieda regulárnych jazykov, generovaných regulárnou gramatikou (Konečný Automat)
LRE
LRE, TS
LCS, LOA
LCF, ZA
R,, KA

Vzťah automatov a jazykov z
Chomského hierarchie

Teoretické základy informatiky
Lineárne ohraničený automat
Mgr. Daniela Chudá, PhD.,
[email protected]

Lineárne ohraničený automat – neformálny popis
Výpočtový model reprezentovaný Lineárne ohraničeným automatom:
riadiaca jednotka,
čítacia/zapisovacia hlava
ohraničená vstupná páska.

Trieda jazykov rozpoznávaná LBA

Uzáverové vlastnosti triedy LCS

Chomského hierarchia jazykov
LRE Trieda rekurzívne vyčísliteľných jazykov, generovaných frázovou gramatikou (Turingov Stroj)
LCS Trieda kontextových jazykov, generovaných kontextovou gramatikou (Lineárne ohraničený Automat)
LCF Trieda bezkontextových jazykov, generovaných bezkontextovou gramatikou (Zásobníkový Automat)
R Trieda regulárnych jazykov, generovaných regulárnou gramatikou (Konečný Automat)
LRE
LRE, TS
LCS, LOA
LCF, ZA
R,, KA

Vzťah automatov a jazykov z
Chomského hierarchie