ΠΛΗ30 ΜΑΘΗΜΑ 4.3 (ΕΚΤΥΠΩΣΗ)
0 likes2,943 views
1) Μη Ντετερμινιστικό Αυτόματο Στοίβας 1.1) Ορισμός Γλώσσας Ανεξάρτητης Συμφραζομένων 1.2) Ιδέα Πίσω από το Μη Ντετερνιστικό Αυτόματο Στοίβας 1.3) Παράδειγμα για την L={0^n 1^n | n≥0} 2) Μαθηματικός Ορισμός Μη Ντετερμισνιστικού Αυτομάτου Στοίβας 2.1) Ορισμός 2.2) Παράδειγμα Ασκήσεις
More Related Content
What's hot (20)
Viewers also liked (7)
More from Dimitris Psounis (20)
Recently uploaded (8)
ΠΛΗ30 ΜΑΘΗΜΑ 4.3 (ΕΚΤΥΠΩΣΗ)
- 1. 30 4: 4.3: !" # $ % # & ' # ! "# $ % & ' ()& * + * #) , , - * #) , , ' . # ' * #) , /$ ,& ! " # $% . ( # % # ) % # ! : (!( * + % ' !" # (!( * , (-) (!( * # # ' !" # ( # -! # ' !" # ! " # $% B. . / ! 1. !" # 1. # 01 # 23 # 4 5 2 / !" # ! « ) %» ( - / !5 # " 0 2# # -01 #, * 0 *%: ( 6 - " 0 ( % -01 . ( 786 - " 0 ( * % -01 . ( ) *' - ! # / !" #: !" # ( 4.2) !" # ( 4.3) ! " # $% # 01 # 3 # 4 5 2 / : ! -01 02- ( ) ( ) % 3 4 5 2 / ( .8. ) ( ( - # " 0 2# #. ( ) !" # ( . ) ( - / !5 # " 0 2# # -01 #.
- 2. B. . / ! 1. !" # 2. 6*2 (! / ( !" # &! " # $% !" # 2) * ! )2 !!!! !" # !5 /# !" # ( ( '( (% # %# 8/ !# 4 5 !" #. 9 ! 0- (%# ( ! #: • ! * ! - % )/ !# 4 5 , • . ( - 2 !" # ( - / !5 # " 0 2# #. : ;!5 #: • # " # !5 ( ! * ) ! # !" #. • # !" # !5 ( ( 1 0 -! # ! ) # - %# )/ !# 4 5 . B. . / ! 1. !" # 3. * - + %# ' !" # '! " # $% 1: ! M !" # ( - / !5 # " 0 2# # -01 #: ! !: 1 4 ! - % )/ !# 4 5 ( ( - # " 0 2# # -01 # " # $ " #" : • • !" # ( '( : • # q0,q1,q2 ! ( !* # • " ( q0 q1 ! ( !* • " ( q1 q2 ! ( !* ( () ( ,%0)&S%0 ( ( ,%0)&%0 ( ,S)&0S1 ( ,S)& (0,0)& (1,1)& 4 2 - # - %# ( " 0 * ) 4 2 * - 4%# - ' " 0 # -01 #. B. . / ! 1. !" # 3. * - + %# ' !" # *! " # $% ' ( !: ( 5 ( 1 0 -! # - %# )/ !# 4 5 : (! # " # ! 0 % ! q2 0 1 . / ) . . 0 / " , + , $ - " ! - " ! " . $ " . $ # $ , / + 0 !,"1 , ! /! $ .2 0. B. . / ! 1. !" # 2. * - + %# !" # 3! " # $% ) $ " * # *2) # 5 ! ( * - 20 # - ( # - 2 # " 0 2#. + 5 2 ( ( ( !5 "% -"% # " # ( -! ' " 0 ( 02 ( " 02 #. )%! $ !) % 20 ( * - ! ( )! , ( ! ( 1 ( -/-% # - %# .). - " 0 0011 0 0 1 2 1 * , , ) % ! ) % & ) % ) % & ) % & $ 4 562#
- 3. B. . / ! 1. !" # 3. * - + %# ' !" # 7! " # $% ) $ " * # .). - " 0 001 0 0 1 2 1 * , , ) % ! ) % & ) % ) % & ) % & $ 45 8 # B. . / ! 1. !" # 4. * - + %# ' !" # )! " # $% 2: ! !" # ( - / !5 # " 0 2# # -01 #: ! !: 0 , - % )/ !# 4 5 ( ( - # " 0 2# # -01 # ! : • ' ' • ( • ( )(* • ( ( () ( ,%0)&S%0 ( ( ,%0)&%0 ( , )&' ' ( , )& (b,b)& ( , )&+ ( , +)&)(* ( , +)& (c,c)& B. . / ! 1. !" # 4. * - + %# !" # ))! " # $% ' ( !: ( 5 ( 1 0 -! # - %# )/ !# 4 5 : , , +, + )(* . (! # " # ! 0 % ! q2 0 1 . / ) . . 0 / " , + , $ , , - " ! , ' ( - " ! ( " ( )(* - " 3 )(* # ( - " + " , , . $ , " ) ) . $ ) " " * * . $ * # $ , / + 0 !,"1 , ! /! $ .2 0. B. . / ! 3. # # / ' !" # 1. ( # ( #) # ' !" # )! " # $% #: 9 !" # ! ! 7- * M=(Q, , , q0, Z0, *, F) 7( : Q ! ' 0 / / ! 04 " / " 0/ * ! 04 " / " 0/ !" # ! ) % ! ) ' " 0 / ' ! " # ((.). *(q1, , ’)=(q2,w) ( ! ! q1 * " 5 ( ! * !" 2) ( /-( / ’, 4 ' ( q2 " 5 !" w). ! ' 0 / 0 1 / Qq ∈0 * }){(: Γ×→Γ×∪Σ× QQ εδ QF ⊆ Γ∈0Z
- 4. B. . / ! 3. # # / !" # 2. * - )! " # $% ) #$ $# $ - . . / ( 2 ( : ( !5 /# 7 * : M=(Q, , ,q0,Z0,*,F) ( : • Q={q0,q1,q2} • ={0,1} • ={Z0,0,1,S} • q0 ! ) % • Z0 ! ) ' " 0 / ' • " #: 1. *(q0, ,Z0)=(q1,SZ0) 2. *(q1, ,S)=(q1,0S1) 3. *(q1, ,S)=(q1, ) 4. *(q1,0,0)=(q1, ) 5. *(q1,1,1)=(q1, ) 6. *(q1, , Z0)=(q2, Z0) • F={q2} ( () ( ,%0)&S%0 ( ( ,%0)&%0 ( ,S)&0S1 ( ,S)& (0,0)& (1,1)& . % # 4 -% 1 $1 !" # - -01 : 0 1 2 3 )! " # $% . % # 4 -% 2 $1 2 !" # M ( - / !5 -01 L2 = {ambbam+1 | m ∈ Ν, m ≥ 1}. )&! " # $% . % # 4 -% 3 A) *1 - % 3 4 5 2 / - -01 L = { xcy : x,y ∈ {a, b}*, |x| = |y| }. ,) ) * !" #, ' 4/ . 1 8.2, ( - / !5 -01 L. *1 0 -! ! * " 0 abbcaba. )'! " # $%
- 5. . % # 4 -% 3 ) *1 0 -! ! * " 0 aca. $) *1 0 -! ! * " 0 abbcaba. )*! " # $%