Loading 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

Matematyczny świat języków: 2. Języki regularne

No description
by

Michał Korch

on 10 May 2017

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Matematyczny świat języków: 2. Języki regularne


MIMUW

Matematyczny świat języków
Michał
Korch

Matematyka dla ciekawych świata
Cz. 2. Języki regularne
Jesteś rycerzem i Twoim życiowym celem jest
ocalić piękną królewnę i dostać jej rękę i królestwo.

Znnadujesz się na drodze na środku pustkowia.
Droga wiedzie w kierunku N i S.
Gdzie się udajesz?


N S
Docierasz do rozwidlenia dróg. Jedna prowadzi przez pustkowie, a druga przez las. Obie dalej na północ.

Gdzie idziesz?


przez las przez pustkowie
Jest bardzo zimno, ale nie ma tu czym palić.
Nie możesz rozpalć ogniska, jesteś zmuszony zawrócić.
W lesie drogi się rozwidlają.
Możesz pojechać mało
uczęszczaną ścieżką w lewo
lub bardziej uczęszczaną w prawo.
Lewo Prawo
Na środku ścieżki sptykasz kości.
Ewidentnie ludzkie.
Jedziesz dalej Zawracasz
spotykasz strasznego potwora.
Straszniejszego niż Ty :(
GAME OVER
Wyjeżdżasz z lasu.
Na horyzoncie widzisz góry. Z drugiej strony
widać ruiny zamczyska z dużą wieżą.
Góry Zamek z wieżą
W górach drogi się rozwidlają.
Możesz pojechać mało
uczęszczaną ścieżką w lewo
lub bardziej uczęszczaną w prawo.
Lewo Prawo
Spotykasz jaskinię, która okazuje się
być magicznym teleportem.
Widzisz klasztor
górskich mnichów.
Co robisz?
zawracasz wchodzisz
mnisi Cię nawracają i zostajesz tu do końca życia
GAME OVER
Spotykasz ogromnego smoka.
Co robisz?
zadajesz trudną zagadkę

wyciągasz miecz
Zaciekawiony smok leci do smoczej biblioteki,
by znaleźć odpowiedź, bo
sam nie może do niej dojść.
Możesz uwolnić księżniczkę z wieży
GRATULUJĘ!
Smok okazuje się
straszniejszy od Ciebie:(
GAME OVER
Natrafiasz na duuuże jezioro.
Od której strony chcesz je obejść?
od lewej od prawej
spotykasz żabę, co robisz?
cmok ignorujesz i idziesz dalej
To księżniczka!
GRATULUJĘ!
Zabłądziłeś.
Trafiasz do jakiegoś lasu.
Automaty
b
bbaabaa
bb
baabaa
bbb
aabaa
bbba
abaa
bbbaa
baa
bbbaab
aa
bbbaaba
a
bbbaabaa
a
aaa
aa
aa
aaa
a
aaaa
a
bb
ab
b
abb
bbbaabaa
aaaa
abb
Co to?
alfabet
{a,b,c}
stany
P
Q
T
R
U
S
V
a
b
c
c
b
a
b
c
a
a
b
a, b, c
a
c
b
c
a, b, c
stan początkowy
przejścia
stany
końcowe
abca
abaca
acbab
aabbcc
ccba
język wszystkich słów, które
zawierają frazę abc lub cba
{0,1,2}
R0
R1
R2
0
1
2
0
1
2
0
1
2
suma cyfr w słowie dzieli się przez 3
z resztą 1
{a,b}
automat rozpoznający wszystkie
słowa mające parzystą liczbę a
Język jest
jeśli istnieje automat go rozpoznający
P
N
a
b
b
{a,b}
automat rozpoznający wszystkie
słowa mające taką samą parzystość liczby występowania a i b
PP
a
NP
PN
NN
a
b
b
{a,b}
automat rozpoznający dokładnie
te słowa, które mają tyle samo liter a i b
nie da się!
Załóżmy, że znaleźliśmy taki automat.
Ma on pewną skończoną liczbę stanów N
aaa....aaabb...bbb
N+1
N+1
P
K
S
S
k
aaaa
k
S
Skończone
nie wszystkie języki są regularne!
lemat o pompowaniu
a a b b b a
a
a b b b a
a

a
b b b a
a

a

b
b b a
a

a

b

b
b a
a

a

b

b

b
a
a

a

b

b

b a
{a,b}
automat rozpoznający dokładnie
te słowa, które mają tyle samo liter a i b
nie da się!
Załóżmy, że znaleźliśmy taki automat.
Ma on pewną skończoną liczbę stanów N
aaa....aaabb...bbb
N+1
N+1
P
K
S
S
nie wszystkie języki są regularne!
lemat o pompowaniu
a
P
a
a
S
a
a
a
a
a
a
b
b
b
b
K
aaaa
Automaty niedeterministyczne
P
a
ab
Ś
a,b
a
b
a,b
a,b
a
P
a
P,a
b
a
P,a,Ś
b
P,ab
a
b
P,ab,Ś
a
P,Ś
b
a
b
a
b
wszystkie słowa kończące się na ab
Wniosek:
Każdy język rozpoznawany przez automat niedetministyczny jest też rozpoznawalny przez pewien automat deterministyczny
Wyrażenia regularne
a,b
+
.
*
puste słowo
pusty język
a+b
={a,b}
(a+b).a
={aa,ba}
((a+b).a+a).b
={aab,bab,ab}
a*
((a+b).b)*
(b*.a.b*.a)*
język słów o parzystej liczbie liter a
Twierdzenie Kleene'go
Język jest regularny wtedy i tylko wtedy, gdy da się go zapisać wyrażeniem regularnym
Stephena
1909-1994
domknięcie Kleene'go
twierdzenie Kleene'go o punkcie stałym
algebra Kleene'go
1. Mając wyrażenie regularne możemy znaleźć odpowiadający mu automat
2. Mając automat możemy znaleźć odpowiadające mu wyrażenie regularne
((a+b).b)*
a
b
b
b
a
a,b
P
N
a
b
b
Full transcript