• Ei tuloksia

kielet äärelliset

N/A
N/A
Info
Lataa
Protected

Academic year: 2022

Jaa "kielet äärelliset"

Copied!
5
0
0

Kokoteksti

(1)

!""#

$%&'()*%+),-. /'0) '& 1'/2*),( 013,%1, 2('4-,/0 +(, *%0'-5+4-,6 7% &+1) +11'(89

3%: )' ;31,<0 )=,'(,/ %,+(-. +-- 2('4-,/0 +4'*) &*%1)3'%+-3)3,0 '& 2(':(+/0 >)=,3(

0,/+%)31 2('2,()3,0? +(, *%0'-5+4-,6

@ABA@ CDEFGHI JKLMENO LP QRKGHI ODSTGHNU

V=,'(,/W X+%:*+:,

Y Z [\]^ _` =+-)0 '% 3%2*) ^a

30 (,1*(035, ,%*/,(+4-, 4*) %') (,1*(035,6

bcddefX,)<0 g(0) 0='h )=+) -+%:*+:, Y 30 (,1*(035, ,%*/,(+4-,W

i

$%35,(0+- /+1=3%, `j 1+% 4, ,+03-. /'83g,8 )' + /+1=3%, \]^kh=31= 03/*9

-+),0 1'/2*)+)3'% '& ` '% 3%2*) ^ +%8 h=31= =+-)0 '% +11,2)3%: 0)+),k 3& )=,

03/*-+),8 1'/2*)+)3'% =+-)0 +) +--6

X,)<0 )=,% 0='h )=+) -+%:*+:, Y 30 %') (,1*(035,W

i l

*22'0, )=+) h, =+8 Y Z mn`op &'( 0'/, )')+- V*(3%: /+1=3%, `o6

i

X,)<0 +-0' +00*/, )=+) /+1=3%, `o -,+5,0)=, '(3:3%+-3%2*) '% )=, )+2,kh=,%

3) =+-)06

i

X,) `j 4, )=, *%35,(0+- /+1=3%,kh, 1'%0)(*1),8 ,+(-3,(6

i q

'h h, 1'*-8 1'%0)(*1) + )')+- /+1=3%, &'( r 4. 1'/43%3%: /+1=3%,0 `o

+%8 `j 3% )=, &'--'h3%: h+. >83+:(+/?6

i s

*) h, t%'h )=+) 0*1= )')+- *%35,(0+- /+1=3%, &'( -+%:*+:, r 8',0%<) ,u30)v

w'%)(+831)3'% x Y 1+%%') 4, (,1*(035,6 y

x w'('--+(.W X+%:*+:,

z

Y Z [\]^ _` 8',0%<) =+-) '% {a

(2)

*5+ 6 W $%35,(0++-3t3,-,% r )*%%30)+/3%,% t'%,,% `o +5*--+6

@ABA DON M DUSDE

w'((,02'%8,%1, 4,)h,,% V*(3%: /+1=3%,0 +%8 1'//'% 2(':(+/0W

V*(3%: /+1=3%, &'(/+-30/ 2(':(+//3%: -+%:*+:,

V*(3%: /+1=3%, 2(':(+/

w'8, '& V*(3%: /+1=3%, +00,/4-,( (,2(,0,%)+)3'%

$%35,(0+- /+1=3%, +00,/4-,( 3%),(2(,)+)'(

i s

,1+*0, ,5,(. V 1+% 4, 3/2-,/,%),8 +0 +01+- 2(':(+/ +%8 531, 5,(0+k )=,

(,0*-)0 &'( V<0 ='-8 83(,1)-. &'( +-0' +01+- 2(':(+/06

i

'( ,u+/2-, =+-)3%: 2('4-,/ 3%),(2(,),8 4. +01+- %')+)3'%W )=,(, 8',0%<)

,u30) )')+- +01+- 2(':(+/kh=31= 8,138,0 3&)=, :35,% +01+- 2(':(+/ =+-)0

'% :35,% ^6

!"#!$%

X,)<0 0*22'0, h, 1'*-8 /+t, + )')+- +01+- &*%1)3'%W

&'#()' Y>

*+

^ W ,-.,? W /dd0- 12k

h=31= :,)0 5+-*, (&k 3& )=, 2('1,8*(, 8,01(34,8 4. 0)(3%: 2+(+/,),(

*

=+-)0 '%

3%2*) ,03))3/3 ^k +%8 !$" ')=,(h30,6

X,)<0 %'h h(3), +%')=,( +01+-92('1,8*(, Y4W

#5&

4 Y>

*

W ,-.,?6

&'#()' Y>

*+

^ W ,-.,? W /dd0- 126

7)' 8

*%1)3'% Y 9

(3)

'56

7)'

8+3% 2(':(+/9

) Yn

*+*

p (' )$ (& 56

'56

X,)<0 8,%'), 1'8, '& Y4 4. 4 +%8 0)*8. )=, 1'/2*)+)3'% '& Y4 4. 3)0 'h% 1'8,6

, :,) 0'%)(+831)3'%W

4

Y n4p =+-)0 Yn4

+ 4

p Z !$"

Y4n4p 8',0%<) =+-)6

l

' + )')+- =+-)3%: 1=,1t,( 2(':(+/ Y 1+%%') ,u30)6

@ABA HULEDMGEGF LP UNODHFGS JKLJNKFGNU

=+) +(, 0,/+%)31 2('2,()3,0

=+) +(, )(353+- 2('2,()3,0

;31,<0 )=,'(,/6

@ABA FTNK RHULEDMEN JKLMENOU

i

'"$!)$)( 5)#!( #!$#&$&"

&#&)'7

V=,(, 30%<) +-:'(3)=/k h=31= 0'-5,0k 3& )=, :35,% 6 '(8,( 2(,831+), 1+-1*-*0

,*+)3'% 30 5+-38 >-':31+- )(*,k 1+% 4, 2('5,8 &('/ +u3'/0 '& 1+-1*-*06 ?

y

i

)$( " $

!()!")("!)" )'"' &('! !"#

V=,(, 30%<) +-:'(3)=/k h=31= 0'-5,0k 3& )=, :35,% 3%),:,( &+1)'(,8 2'-.%'/

n{$

+%%%+

{&p30%*--+4-,4. 3%),:,(5+-*,0'&5+(3+4-,06>36,60*1= n

'

$

+%%%+'

&p (

)

&

k &'( h=31= n

'

$

+%%%+'

&pZ *??6 +-(,+8. *%0'-5+4-, 3&)=, %*/4,( '&5+(39

(4)

i l

'/, 3/2'()+%) 2('4-,/0 +4'*) &'(/+- -+%:*+:,0 +(, *%0'-5+4-,6 X,)<0 =+5,

:(+//+(0 +%8 3% 0'/, -,5,- '& )=, w='/0t. =3,(+(1=. +%8 0)(3%: ^6

7% )=, )+4-, 0'-5+4-,k %') 0'-5+4-,k +-h+.0 )(*,6

V+0' W

('4-,/W 30 - *

^ ( mn p

mnp Z

mnp Z

mnp Z mnp

mnp mn p

mnp mnp Z

mnp (,:*-+(

mnp mn

p '& ).2,

mnp '& ).2,

(5)

{a b c | i=j tai j=k } i j k

kielet äärelliset

tunnistus:

äärellinen automaatti (rajall. muisti) k k

k {a b }

{a } kontekstiton kielioppi

tunnistus:

epädeterministinen pinoautomaatti

{ww } R

kielet, joilla on yksiselitteinen rajoitettu

i i i {a b c | >=0 } tunnistus: Turingin kone, jonka tyotila lineaarisesti

Kontekstiset kielet

Kontekstittomat kielet

Säännölliset kielet =lineaariset kielet

deterministiset

pinoautomaatti kontekstittomat kielet

tunnistus: deterministinen Ratkeamattomat ongelmat ei ole olemassa edes hyvaksyvassa tapauksessa

pysahtyvaa Turingin konetta Universaalikielen komplenmentt:i

kone−syote−parit, missa kone ei hvaksy syotetta

Rekursiivisesti numeroituvat kielet tunnistus: Turingin kone, joka pysahtyy ainakin

hyvaksyvassa tapauksessa

Universaalikieli:

kone−syote−parit, missa kone hyvaksyy syotteen

tunnistus:

universaalikone Rekursiiviset kielet

tunnistus: totaalinen Turingin kone

Viittaukset