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: 3. Języki bezkontekstowe

No description
by

Michał Korch

on 1 May 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Matematyczny świat języków: 3. Języki bezkontekstowe


MIMUW

Matematyczny świat języków
Michał
Korch

Matematyka dla ciekawych świata
Cz. 3. Języki bezkontekstowe
Gramatyki bezkontekstowe
Zdania w angielskim
Sent -> Subj Verb Obj | Sent Conj Sent
Subj -> Art Adj Noun | Art Noun
Art ->
the
|
a
|
an
| -
Adj ->
black
|
good
|
happy
Noun ->
girl
|
cat
|
computer
|
it
|
she
Verb ->
has
|
likes
|
talks
|
takes
Obj -> Art Noun | Prep Art Noun | Adv | Obj Obj | -
Prep ->
for
|
to
|
on
Adv ->
fast
|
often
Conj ->
and
|
but
|
because
Sent
Sent Conj Sent
Subj Verb Obj
because
Subj Verb Obj
Art Adj Noun
talks
Obj Obj
Art Noun
likes
Art Noun
the
happy
girl
Prep Art Noun
Adv
-
she
-
it
to
the
cat
often
the happy girl talks to the cat often because she likes it
alfabet
symbole robocze
symbol startowy
reguły
symbol roboczy -> słowo złożone z
symboli roboczych lub liter z alfabetu
może być kila reguł dla każdego symbolu roboczego
słowo jest
zgodne z daną gramatyką
, jeśli da się je z niej wygenerować zaczynając od symbolu startowego
język generowany przez daną gamatykę
, to zbiór wszystkich słów, które są z nią zgodne
język nad alfabetem {a,b} złożony ze wszystkich słów, które mają dokładnie tyle samo liter a i b.
X -> X
a
X
b
X | X
b
X
a
X| -
X
X
a
X
b
X
-
X
b
X
a
X
X
b
X
a
X
-
-
-
-
-
-
ababba
Język jest
y
jeśli istnieje gramatyka bezkontekstowa, która go generuje
Palindromy
{a,b,c}
np.: aabaa, acbbca, aaabcbaaa
P ->
a
P
a
|
b
P
b
|
c
P
c
| Ś
Ś ->
a
|
b
|
c
| -
aaabcbaaa
P
P
P
P=Ś
Wyrażenia arytmetyczne
0001
(((4+2))+3)
tylko te, co dają wynik podzielny przez 3
Ale czy każdy język jest bezkontekstowy?
nie!
{a,b,c}
Język wszystkich słów postaci a...ab...bc...c.
n
n
n
Dowód: Załóżmy, że znaleźliśmy gramatykę bezkontektową, która generuje nasz język.
Jest też w nim jakaś najdłuższa reguła, powiedzmy, że ma M symboli.
Jest w niej ileś symboli roboczych, powiedzmy N.
aaaa.....aaaabbbb.....bbbbcccc.....cccc
S
najw. moż. rozgał to M
co najmniej
N+1
X
X
S
X
X
X
to słowo też zostanie wygenerowane przez gramatykę
a nie powinno być!
sprzeczność
!
Automaty ze stosem
alfabet
{a,b}
stany
stan początkowy
stan(y) końcowe
L
Ś
P
K
symbole stosu
{a,b,#}
#
symbol
początkowy
przejścia
a
,#->a#
-
,#->#
b
,#->b#
a
,a->aa
b
,a->ba
a
,b->ab
b
,b->bb
-
,a->a
-
,b->b
-
,#->#
-
,a->a
-
,b->b
a
,#->#
a
,a->a
a
,b->b
b
,#->#
b
,a->a
b
,b->b
b
,b->-
a
,a->-
-
,#-> #
abaaaba
a
baaaba
ab
aaaba
aba
aaba
abaa
aba
abaaa
ba
abaaab
a
abaaaba
a
b
a
palindromy!
Język nad alfabetem {a,b} składający się ze słów z tą samą liczbą liter a i b.
#
{a,b,#}
a
,#->a#
b
,#->a#
a
,a->aa
b
,a->-
a
,b->-
b
,b->bb
-
,#->#
aababb
a
ababb
aa
babb
aab
abb
aaba
bb
aabab
b
aababb
a
a
Tw. Język jest bezkontekstowy wtedy i tylko wtedy, gdy jest rozpoznawany przez pewien automat ze stosem
(czyli dla każdej gramatyki bezkontekstowej istnieje automat ze stosem robiący to samo i na odwrót)
zbudujemy z danej gramatyki automat
{0,1,2,3,4,5,6,7,8,9,*,+,(,),W,L,C,#}
#
-
,#->W#
-
,W->L
-
,W->W*W
-
,W->W+W
-
,W->(W)
-
,L->C
-
,L->CL
-
,C->0
-
,C->1
-
,C->2
-
,C->3
-
,C->4
-
,C->5
-
,C->6
-
,C->7
-
,C->8
-
,C->9
0
,0->-
1
,1->-
2
,2->-
3
,3->-
4
,4->-
5
,5->-
6
,6->-
7
,7->-
8
,8->-
9
,9->-
+
,+->-
*
,*->-
(
,(->-
)
,)->-
-
,#->#
(2+3)*14
W
*
W
)
W
)
+
W
L
C
2
L
C
3
L
C
1
C
4
a
Full transcript