!""#
$%&'( '
)' (*'
" '' '(
" ! ' *'&'
" ! ' '(
" ! ! )&
" ! #
" ! &
" ! '
" ! $'' !
! &'&'$''
! $ & "
!!" # !$ %
! & '()%%'
! ! ' !
! # '&' &' !
! &'&' *('(' &' !*
! +& &*% !
! $ & #"
!!" " ! !!" $ "
# ' '&& % & #!
# ' '&& ' #
# ! (''% #
# ! ' #
# ! ' '(' "
# ! ! ' (
# #
# # *&' *
# # ! ' )
# *'' '
# '
# ! '' *''
# # )
# )'( *'
# '& #
# ' % '' &
# '& ' ' & '&'
# ' & %&'' *"
# * &'&' ' & '&' *
# * '' *
# * ! +'('*& ' *
# * # &'& ((' *
" $ " ! " $ "
&' &*% & *
' &% &&' &* !
! && % ' ' &* #
! &'&' '&* ( (''
# "
#
' (% * #
# ! ''% *'' * *
** %'('
)
! )'('* ""
# )'('* ' "
* ''((' "!
&''' %' "#
)&** "#
! )&*%'('% "
# )&** ( "
*&' *&&%&
'$ %
&& "
)&* &''' %'% ')
('' "
** && ) "
* ''$ '$)% &&)%&&% '& !
)& ''&' #
)%'('
' '&(
* &* !#
&' & '&' !
! & % & !
&' & %&'' !
" &' & '&' #!
"#" " $ $ " !
)$ ' #
! $ & #
! ( "
! ! $ & '(' '(& #
# $ & %&'
# ' &
# ! ' &
# # *'' &
%% &&'' &* !
$ $
& &' & #
! &' & &''' &
# &'
('& % '&
$ & &' &&'& %
! '&& )&''' ' &'
# ('& &' *"
&'&' &' % &' &'' *
&'' % &''' %& )
&'' *
# %' *
&' &'&' *
$ & *('(' *
! ' ' "
# ' '&' &'
& #
) '&% &
*
& *&'
'& '
# *& &''
'' * *%&( '&' %
)('' '
* '&' ' ' %
&' &' ' & '' &(
$''*' & ** '& )
**)' & &''% '& &&
! !) $"
%
"
#' %' ! ' & )
$%&'()%*+,-.('&/.
) 0* 0 ' *
$& ) 0"
(*&&- &(,*-.(&
' ''*
&'' ' **' % & '&%&'!
% %&'' !! *' " % **'*&%'
! *''
! $& '&%&' % '' & &&'! %
%&'' ! % &&' ( * *''
# **&&!% ' ((( (&' &*''
(*&&-%./*-%%-
( ' &''&%! %&& '' &%' &'
& &&'' *&' '(&'' &')
*
"""
' %' *'
"
**
' '* & ' (' &'')
!% &( &
-*+
% -&(
( ..%
'& !'(*'!$%&'( '
' ) ( '&! '!&
" ' $( * '&&!)
&' '&&% % ! *& '**
" !$
' $)
(! '! * ')'(! !"" +' *')
! ' '( & *&' + *' * %
& ( *
" $" $( * '
" "$" " ' $( *!
!)! ''&&!*% *'!)
& *' &
$( *! *
"
! *
$
' ' ' $( )
*
(*&&- &-&.
$&' ' '%&
$ ' '% ' & '& &' &)
'((&'
&'& ' '( %& ' &&% % ')
'! & '( (&'(( ((
$ '' &'! & &&% &('' &* )
& && ' '% &
& ' &
&'& ((' &'& &&% '' ''
! '& &''&'& &&% '&'''')
&' ''&&' & & %
&!% '%&& '& % *'
# & % '''( '(
( & ' &&% &' '& %&' '
''('
&!% '%&& '& % (
('(' *('((& % && '(
&' &''
' '&( && ' &
kielet
kontekstittomat kielet kontekstilliset kielet
tyyppi 0
tyyppi 1
tyyppi 2
tyyppi 3
äärelliset
ratkeamattomat ongelmat
esim. pysähtymisongelma tunnistus:
tunnistus:
Turing−kone + ääretön työnauha (pysähtyy aina)
universaali Turing−kone (pysähtyy ’kyllä’−tapauksessa
tunnistus:
pinoautomaatti säännölliset kielet
tunnistus:
äärellinen automaatti
RAM−kone ohj.kielet
, Turing−kone +
äärell. työnauha
luonnoll. kielet?
(rajall. muisti)
)
esim. palindromit rekursiivisesti numeroituvat
kielet
rekursiiviset kielet
rajoittamattomat kielet
'&( && (( &'' & &
((** #
&'*' ' &
((** !
((**
& (
((** "
&* &
' ''('
)
'' '(
' *'&' &'
'&' % &'
! ' % '' &
' '&& % &
'' '
'
*'
' & %&'
# *% %'
&' &*% &
&''' %'
&*
)
$ & % % &
$ &
%&' '% ' &
*'' ) '' &
&'&' &&'' &% ' & %'('
& '&'&! '&% )&
&'&' &' '& ) ' *( %
&
% *'
'& '
$ & &)% '
)('(('
$'' '' & ((' % '' &' & '
'(! %&! % &! %&&% ' % ()
' '& ' ((' ' ''
$
,,-&-%
&
,
/ -.%
&& % '' '!%& &%& ')
'&&' %'! * ' '' $ '
% ' ' '! &' **' ' '
*
*' %&'' !
%& ' ' %)
&'' !
'& ' !
%' !
%' % %'
'&' ' '( !
!&&!%&'')
& "
! ''!%& '&&'!#$# % & %&'
' ' * ! "#$# % & %& ' ' *
(
,(',.
) && %& ! '&&' * + ,-.$-/$000$-12
3 + ,-$4$5$000$62 & -7 % * -7 & %&& * )& &')
*' 89
:! %& '' ( & ; '(()
' ** && !%& &' &&'! '&&'
' &! <! &%&
)&&% ' '
* = * > = !## % * ? # % =
* = * = * > = * + =
* % = 89 * = + ,## % * # % =2
* % = * = + ,## % * # % =2
* % = * = + ,## % * # % =2
*
*'%&'' * + *
* % =
* = + ,#$ # % * % =2$ '' &&
#$
8
%& *
* + , > *2
' %'* + ,-$4$52!* + ,:$,-2$,42$,52$,-$42$,-$52$,4$52$,-$4$5220
/%% .-,.
& & ' %& & ' ')
'&&' %&&% * % = ) %&
* = '%&&
+ ,-$4 - %* 4 % = -$4 20
'&&' & * % = ' &% % '%
-$4 !%' % %' 4 + - 0
$ &' *' , $ $$ $$ $0002 > * =
.
> = *
.
+ , 4$- -$4 % 20
(
' .-,.
&'*'! %& %& %&' &
' %& ( & & ''
" !$
* =
> * =
8 9
A
B
f(A) f(x1)=f(x2) x2
x1
. .
.
f
! & (%&&! 0%&&! %&&
%&! &'& ' % '! & ' *'! & '%&! &'& &&
0 *' && ''
8
9
) *
# =
!# % * " % = #$ %
0
88 9
) *
#
8 =
!# % *$!.$/ % =#$. %
#$/ %
. + /0
* ? =
8 *
=
& &
& *' # % * *' % =! ' #
& +
# #$ %
)' > *! %&&
&%&&
+ ,
# # % 20
&
* ? = (%& * &%&&
*
)&&
.
.
+ ,#
# % 2$
''
.
&'
.
!%' .
( &
& &'*&'
! % ! %&
''
&
* ? =
" "!%'%&' %& &)& (&' &&
!#.$#/ % *
#. +
#/ #. + #/ 0
"
!%'%&' = & && *''
! % ="# % * +
# 0
" "!%'
'& '%& %&
$
%&
&'&
'
?
,2!
# + # '%&! %&
' !
? !
# + .
%&! '%&
' #
<
? <
!
# + # /
%&!%& &'&'
+
(/*,-.( ((&
" !$ )
& ?
+ ,
% &20
''' % & '' %%' % &' '
+ ,#$#.$#/$0002 '&&' * ' &% %&&
+ ,$$$0002 !' %&
& ?
+ 0
)' !' 8
'&&' &% %&& <
0 1 2 3 4 5
2 3 0 1
−3 −2 −1 N
Z
#'&&' &&' '
,-&.(&//./-
'' ' % ((' ''
$ " " "
'! %& * && '
+ ' &'' '''
'*' + $'! * *&'''
! '&'& $'! && ?
' !'! * && % & *!%' '
&'& !' *' % '&'& '
('
&! * &&
&' *&''' +
"$ "
37. 1
+ 1
1
/
!
+ 3 1
7.
+ +
" % &
+
3
.
7.
+ 000
3
7.
+
/
3
.
7.
+
/
+
.
.
/
" " " "!! !" " !!
' %' ! & % '
& ' % '! '
' *& ' ! *' &
! & ' %
"$ "
8
& '' '' &&' '!%
( ' *''
" "!! " $"
' %' ! $' ' '% &
' %' !
+ % ' &'*&' & %
% ( % ( '' ! & '
%
" " " !"! " "
& '' # % !% * % & % *
%'&' ' '
&''''' "# % # &' # ! ! &&)
' % &'! ''
(' *
' % ! %& &&* & &
''
('' !# % # ' # ' % '!
' && + ,# % # /
# + 2% + ,# % # 2
+ +
" " $"
!# % # ' *&' )
' ** & &&' ' (&'& '')
&&%&' !% * '&&' &&'
*'! &'& '&&' * '
$'')%%'(' &&%!% '
%%'(' ! ! % (
& &' ' & (
/
%
)'%%'('&!' &% $$$$000'
&
''
' ' & -!
% - + - '
!
+
&& () % &'& ' ')
' &% '&' !
'%% 1
+
+
( 1
+
! 1
+
+
/
'
$
$000$
/
%
''
/
' ' &
-!%
- + - %
' & -!%
- + - $
%& ''
+
.
+
! &'&
+
$'' &% ()% &'& '
+
+
&-,
+ '* &% ' &' &% ''&&' *''&)
&' '
''&'&'-!%
+ -
& * &( 4 4
-! %& & 4 -)&' *'' &'** 4!"
"
! %')
' 4 ' - & $)* ' *' ' &%! '
+ #$%
&'()
$! /
+
!
+
( +
/
. ' )& ' .' &' &' %&&
& %%' %%'(&' . *' 9
&'' ! %& * % = ( ! %' ''
%&
* ? = ' & ( && * & % %&'
= & ' ' (&' * & . '' .
' &!%& * &
$' ''
%&!%& &' . &
&
-/*.- ),./-
. '' ( &' )
''
!%& ' $$$$000
'& *&'! (((& ' !
& &&%%& & '&&'! ''
'!(&' &''& ''!% '* (&' ' &
% *'+' '% ' !%& ' (%&)
' ' ' ' !%& *' ' (%&' '%
' ' % * %' '*
&% ' (
'% ''
' *' ' %
'
* ' '* %%'( '%
/
!
%* ' $ '& %'&*' &&
% . . ' ' &! %& '' &')
%%&& ' %%'(
%.,*- %*(/..-
' *#! ''' '' . *'
' ' ' '! &% %&& ()
'% '
& ''' ''
&' & . *' '&)
''' &( &&& '
'&' **!
' '&'
"
% %&& < (
" & % < '%&& % '! ' ()
+'+ $ $' ' &&&)
#! # ' && # %%'(' # '
%&
$? & &! ' ' $
' !%'' && ' & ' &
'( && ' & ' ' '
0000
0 000
0000
0 000
0000
' ('&'' '
%%'(&''' % %& %&'& '&' $' '
'&'' 0./
000
' ' 7 +
'
' & ' '' '&&' 0000 $ & &&
'( '''! ' ' *&& %&'' ' ' '
'!! ' ! '!# ' # '% &&
$ & '' ''
! ! && ''& ' '!
' ' ' ' * ! %& '(
'''
-*+%-&((..%
!!' ' 0&'!
"
&!! ')!%'' &((&'+)
(' ''
% ((' '! **& &)
%!%& %& '
$ "! +&! ' ' ''!
"
&!
&&!%& '' '& '
#! !''!0 0 +
0&'!
"
&! & ''' ' **%'' )
! '' %'' & )
' ((&('&&* * ' )' &((&('
& *'&% %%& &((&( %& *'&!
& ('' &'' & (&' &((&(
& &(!%'*'&% ( & '&%% &((&('
( & &&'&% %' &((&(' ( &
' &%! %& &((&( ( *' %&' '
&((&(' &'' *''' & (&' *'
! '%'
'
'
# '&%%&'' '
% ' &% ' ' (%
& ' &%'' !% ' '
%%' ! & & ' '%
''%%'
' '' '&''!%& & ! $&' ()
- + 4 * -! % ' - /
+ -4 + 4 /
*!% ' - /
4 /
+ -4 4 /
) &*& *&%)
! - 4 - 4 + 4- 4 !% % - 4 !% ' - 4 + 4 *&'
! -% 4 !% * +
&& %&& % && + $' &! *')
'%& && + 1
& ''' &'&'''!%& & &&& &''
''
&& &''% & )' + ! '' ' (&' &''
'!* & ' & (! )
' &'' %& *! &&& &'' '' $&')
' &'' %&& +' ' & ' &''
%& ' &)&' *'
'' &''% %&& '* &&& &'' ''
* $' ' )' %'' &!
& & ( (' %''
$' &*')' 5 * &&'&! ( /
5 + * &&'&&'
'& & ' !%& )
&'&' ' &
'&&%&&'& % &'&!&%'&' &&'!()
(&' *&'&! (*'' &'' &''% (*
&' % ' (&' '('*
('* '('* * ('
''' &&'' '()%%'!%& &&&'
&' &' &%' ! %
)%''' (&' &'
(' ' % ' ' '' '' &''
' ' '
)' &&% &% ! ' '
**
! )' ' # '' # & ' &&%! (' (%
&&%! ' * &&% ##
# )' %'' &&%'' '(( ! ' & '
)' &&%'' '((
! ' ' * *' &&%'
% ' ' *' !& '* &' % %
! ' '&' %%' &' )
&'
''&' % &'' ' ( &'& ')
*(
'()%%' '' % ' &''% &* (''
3 + ,$$
2% &**!%& & ' '%
' ''''
# ? #
# ? ##
# ? #
#
? #!
'' # % ' &&%% (' (% &&%
$&'&&' &&& '&&%%%&& 3!%& &')
&&%' ,$$$
$$$
$$$
$
$
$
$$
$
$$0002 ( ' ' &('((&' &&' &)
&%' ' .# &&%% ' &&)
%' # %%' ' /# +& &&% # '
%%' '
'' &('((&' '' %&& &&%)
%! ' ''' 3 '%&& '' (% %&&! & ' %&)
' &('((&' '' ( $' &() &')
' *' &&'
3 ? ,$2 ''%&' &&' &&% %& '&'
"
$' &('(! &&& 3 &&%% *' ()
&'(( $ ' # # + &' .
+ # +''%&&
* &' % ' *' & * ')
'&'
' '' ' & &'
&& ' % &&%
&&
' % &&%
&&
' % &&%
'()%%' &% ' &%'' ! '! 0
*'' %&& '(
&'
!%& && *&' ' &
'
' &&'& % &'&
*&' &&& ' &&'&*
*&' ( '' &*
&' & ' ( &'&
&& (&'' *&' % ' '&'
'&
*/-/ /&-.&
&&& & &' &'' & %)
&'
' &&' &( (' &&% & " %
& & '' ' %
'(' %& &&'
' &'& '( &&' &&'& ' ' &&%)
/*''-+,,-)- --.. -
/*(&'&-../-. +% /*'-.+
! *(% %&& &'
8 '
,$2%
,! 0! 000 ! 2
%%'( % %& &&' &&% '
""" %
""" &&' &&%%!%
$ %
' &&' &&%%
&&% # ' ''( && & # '
+ + $ + + 0
89
*' +
&&%% *'*
%% *&& &)
% *&& &( %'&' '&( )
''&' '( '&&%
(& (&
%' # + % + ! # + % # +
&& # # + # + #
&& #! #+ #
&&' 3 &&& &&%% %&& 3 ' 3 + ,$2! 3 +
,$$$$$$0002
.&,/%. +% ,*%%-. '-//.
('' '& &'
3 ? $
'' 3 % &&'%
*' & '&' &&!%'' &&
*&' ''
&(
' 3 ? ,$2
'&&'*'
& & && ' &)
&' 3 + ,$$$000 $2 &&'
3 ? ,$2$ # +
$ %' # &&
$ %' # &&
)&' *'
3 ? ,$2 ' &&%%&&
* + ,# % 3
# + 2$
' *' %&&!% '' &(
%&' &&%%&& * > 3 ' *'
3 ? ,$2$ # +
$ %' # % *
$ %' # % *
&&' 3
&&)
%%&& * > 3
& *
* &&%%&&
( *'
' & *'
'! % '& !%' && '(
# % '& % ' #
+& &&& ' '& &' %
&'! ! ' &&& &&%% ' %)
& ' % %&& ! &&)
& *' %&& ( . ' %
'
'& '' ('' '' & '
&' %!% '&'
9
& ' &&' 3 &&%% %&& 3 '
&& 3 + ,-.$-/$000$-12 & &&'%%'('!'
-. -/ 000 -1
)& 3 &&% %%' ''
8
' " '&&% !' ' -.$-/$000 $-1!
' ! '%
! && *'( '' &&% &&'%%'(&'''
%&' ' & '' 3 &&% % *)
+ %&
& ? 3
?
? -.
? -/
? -1
? -.-.
? -.-/
? -.-1
? -/-.
? -/-1
/
? -1-1
/
? -.-.-.
/
? -.-.-/
& ' &&' 3 *'%&& (
& &&& 3 *' &&
+ , &' 3 ? ,$220
+' &! ! ' ''
+ ,$.$/$00020
&& 3 &&% &''' %%'(&''' #$#.$#/$000
' ' *'
3 ? ,$2$ # +
$ %' 7#7 +
'& % ! + %& % &
$
# +
$ %' # + # +
$ %' # + # +
'$'''$ ' '! %&& !
. /
#
#.
#/
#
( & +% *&''' & ' ! %' ' '
&&''&' '&&' )%&' )
* ' ( %& '%&&
' * && %&! ' &&&
%)
& ' ' & & '
$ '
' '&'
& &' (' &'&(' )
' 8
98
% % ' '( # * *()
('(' )& '' ' *('(
)%! %& &''! *('((& )% '(
&! ' &% )&
*!
"
!
%& ' !%' &&%* ' & *('(( '(
!%
% *' )&
*
$
"
& & &
%&'
% &' &
'& &&' '
*('((
$
+
*('(
'' '! ' *('('''%
''
&&' 3! ! 000 '% &&&' &%
' &&' 3 + ,$2
&&' && (' %& ' 3
&'& -! 4! 5! 000 * &* ' &%
' & 3 + ,-.$000 $-12 &&' 3+
&&% ! ! !#! ! 000 * *** ' &%
&&%% &# #
&&% *' #
-45+
& # + -. 000-! + 4. 00041 #+
$(% &&%
&&%!%'' &** && - - 1
- 1
+ --000-
1
- 7
45 +
&&% # ' & #
-4 /
+ -4-4
# + #
&&' 3 &&& &&%% %&& 3
,-$42 + ,$-$4$--$-4$4-$44$---$--4$0002
' *''
% (
' **
! $&'''''&&& $&
&'* '()%%'! %& &' '' ')
'
'(' ? '((
'((' ? ''((
' ? '
' ? '('
'' ? '
'' ? '(!
'' # % ' &&%%
$ '! (%'& &&%' '(( &
&' '(%%' '
# $&' &&' 3 + ,$
$2 &&' *''
''
3
+ ,2 (% &&%
3
.
+ 3 3 + ,-#- % 3 % # % 3 2
' 3 .
+ ,$
$2! 3 /
+ ,$
$$
$
$
$$
$2 & )
& ' 3 1
'' & ' && &'' 3 +
7
& %& %! & % ('! %)
& 8
&&%'*&' ' " !# &!
" ! # ' ' &' &&%)
& &'
%
(''' &'&(
!%'&''% '
'''
!% (''%' ')
&%!' * &%% *&'
' '' '&&!% ' '' ''!
% & ( '' ' '*''
' (&'( &&%!%'' '(( ' &'' $' &&%
" '* &%
-" '* &%
' ' &''' '!%&
#& # * &%
' *' &
& ' &*&' ' &&% ' & ! %& )
''% (&'((
&' & * & ('' && * % =
&&' 3 & $
* % = 89 &
* = + ,# % 3 # % * # % =2
* % = &
*= + ,# % 3 # % *$ % =2
*
* ! ! ''
*
+ ,2$
* + ** .
+ ,#.000# #7 % * !
+ $000 $2
* &
*
+
*
3
'
! " 3
# 3
- % 3
! !
3
$
%
$
! & 3
3
' (
3
)*++
,
, + :
," + ,-2
, # + ,-2 - % 3
, %
+ , ,
,
+ , ,
, & + ,
'
,-.42
. + //#0101. / + /#01&.
+ /#0&1.
+ /#/0% /00111&2
3
, . + ,-2,42 ,42+ ,-42,42 + ,-4424
, / + ,-4 2
+ ,-.-4.-4-4.-4-4-4.2222
+ ,-4 7
24
,
+ ,-2,4 2
+ ,-.-4.-44.-444.2222
+ ,-4 7
24
,
+ ,-2,4.44 2
+ ,-4.-44 2
+ ,-.-4.-44.-4-4.-4-44.2222
+ ,# % ,-.4 2
-5! #
6 7 45! 2
!
&
9
5 ! 5
,
%
%
,
%
%
,
,
9
! !
(
!
$
!5
9
.
.
.
' !
"#
$(
%
&&'
""
&
&
$!
5
' (
) *
.
.+.222.,-
!$!
.
&
.
&
.
.
9
.
/
222
.& 0 )
' (
7
) *1
.2.222..
.
.222..3.4.5.222.6,
,.
&
77
&
.
-
77
&
-
77777
,.
&
.
7
9
7
3
4
222
6
! ,
9
.
8
222 9
2
' (
:5
;$/
$ /
5
(
<= >?
<@?
!
!
!
( !
@
;$ 3
/
$
/
' (
@
!
/
7
2 7
2 7
-
=
>
- 7
7
=
>
- 7
/
7
2 77
7
2 77
-
(
=
>
- 77
77
(
=
>
- 77
' (
!
67$67$67$ 6 7
( $6 7
$6 7
( 5
$6
( 7$ 6
7
' 8
9
9
$
)
,
,
,
2
' !
"#
$ 8
! ) +"
&! !
$
$!
,
,
' 3
,
,
' 3
!
5
-
.
.-
-
-
-
.
-
-
-
-
' 3
$
$ - 0 ,
' ,
,
,
,
,
,
' (
6
7
!
$
!
$
)
!
'
, !
$
6 ,
7 ,
)
,
, *
0 ,,
6
"
5
9
9
!$!
!""
$
' 9
!
$
<
+ 7
?
9
.
.+. 7
' .
#
$
.
#
$
9
' .
#
$4
. #
$5
!
6
7
' .
#
$
%
&
!
'
9
!
2
9
!
-
' 3
9
9
(
( 3
5
)
5
'
9
:5
9
!
$
*
+
9
9 !
(,6-.(
(,6-,&-(
(,6-/,&-(
7 +
5
0$!
/
0$!
12
. 34
* 0$!
43
0$!
! -
'(
9
!
)
) *
.
,
!$!
$! $!
'
/
*
-
)
)
)
)
+
!!
+
1
+
4
#1
.
2
+
(
$!
-
$
9
$
!
5!
!
+
!!
,
(
, -
(
9
!$!
'
/
*
+
*
0
*
.
,
,
/
*
0
*
.
,
!
!
,
*
*
0
*
.
,
!
!
,
+
*
0
*
.
,
,
/
*
0
*
.
,
,
*
*
0
*
.
,
5
!
,
6&
(
'
9
5
'
3
4
34
44
/ 3
43
* 4
344
4
344
3
'
(
9
$!
9
9 $
9
&
!
9
!
7
+
!!
9
9
' (
!!
& & & &
6&& 6&&
& 6&& 6&&
6&& & & 6&&
'
)
9
9
!$!
"
"
" " "
"
" " "
"
" " "
"
" " "
" " "
' (
9
""%
&
+*
!
#++
!! &
+
'
&
! 6
!
9
! !!$! ! 7
'
!
"+%
!
#
)++
&
+
50
100
50 50
100
50, 100
50, 100
0 100 q 4
q
q 1
q 3
q 2
'
'
& 6
' (
:5
5
q1
q3
q5 .
.
d
d
E, e
E, e
d d
d d d
+, − q0
q2
q6 q4
)
2 . =.>
)
! *
3.4.222 .6,)
9
9
( !$
!
!
9
!
*
9
* . 6$! * $ & .
3
*
9 +
9
+ *
'
(
*
9
* &
+
4
+((
5
66
/
* 6
+
4
+((
+(( +(
( (
/
* 7
+
/
*
+
+(( +(
( (
66
/
*
+
+(( +(5(
66
/
*
+
66
/
*
+
66
/
*
/
('
9
'
9
!
9
!
5
q0 q1 q2 +, −
d
d
d
'
9
*
9
* . 6 * & .
3
*
9
+ 2
4
.
3
9
+ *
'
(
*
9
* & +(( +(5(
6
+(5( 2
>4
+
7
.
+ > 3
/
* 6
+
7
.
+ > 3
/
* 7
+
7
.
43
%
. = + > 3
/
* /
5 !
!
%
.
!
9
!
+*% )% ))
'
%
!
#
*
&
)
!
9
%
'!&
+*
+
&
+*
+
9
9
9
!
"!"
!
" %%
5
9
9
5
9
5
9
9
9
9
5
9
9
9
9 5
#
!%
&$
"
"
!
"
&
5
!%
"!
!
"
&&
%
!
# ! "
9
!
"#
$
""
&&
"
!
#
!!
)
!
"
&
) %
'!
!!
%
!
)
%
!
#
"
&
!
!
0 "!"
!
"
#
!%
&$
"
"
!
"
&
(
*
4
,
*
,
*
,
4
!
"
&&
0 )
"!"
!
"
&&
%
'!!
""
)
! %"
&
0 )
)
"
!'&
%
"
)
!
!
"
&!
%
&
%
"
3
(
3
!%
0 )
0
"!
)
!
"#
$
!
"
&&
%
!
# ! "
*
0 )
0 ,
(
!
0
*
, 0
! "
&!!
#
&
# "
&&
"
& &!!
+
+
0
0 )
0
)
! "
&! !
0 )
0
0
!
! "
&
%%
$
0 )
$
0
0
$
$
345
+
$
$ = 4
)
)
&
$
$ = 4
)
- )
)
)
*
45
,
) *
,
*
4,
*
,
)
1
2
3
4
5 b
b
a a
a b
b
b a a
&
%
%
)
!
#
&
%
! &&
(
$
$ = 4
+
%
%
(
)
(
*
,
(
(
%
&&'
""%
!&
! "
!&
(
"!
&
(
(
)
(
Deterministinen laskenta
Epädeterministinen laskenta
hyväksy tai hylkää
hyväksy
. . .
.
. .
. . .
. .
.
hylkää
!
"#
$ (
*
)
)
)
0
*
,
*
,
*
,
*
,
*
,
*
,
0
)
#
""
&&
+
+
!
#
&
%
!
%
!
!
#
&
%
!
%
!
"" %
! "
!
#
! !
! !
+
+
+
*
,
$
5
> 4
>
*
3
0
*
,
0
+
-
'
)
"%
$
1
)
1
.)
1
)
)
*
,
*
0 ,
)
0 )
0
*
,
0
)
3
*
,
*
,
"! " "% $
$ = 4
$
0
0
0
*
,
0
0
*
,
0
0
*
,
0
*
,
0
*
,
0
*
,
*
,
0
(
(
-
!
#
&! !
"
#
&
# "
!
#
!!
(
*
,
(
0 M 1 I 2 U 3
M,I,U M,I,U
+
