Q1 Below is the state transition table for a PDA
|
Old state
|
Input read
|
Top of stack
|
New state
|
Operation on stack
|
|
init
|
a
|
Z0
|
init
|
Push
|
|
init
|
a
|
a
|
init
|
push
|
|
init
|
b
|
a
|
Other1
|
pop
|
|
Other1
|
L
|
a
|
Other2
|
pop
|
|
Other2
|
b
|
a
|
Other1
|
pop
|
|
Other2
|
L
|
Z0
|
final
|
non
|
1- Draw the state diagram?
2- Assume that the machine starts in the init state and exit in the final state What is the language accepted by this PDA?
3- Is the string “aabbbb” accepted or rejected?
Q2 complete the following statements?
1-A PDA can recognize………. languges.
2-Transition function in PDA ……………….
3-in 2DFA Transition function is …………………..
4- Transition function in TM ………………………
Q3. consider the context grammar G defined as
X®0Y1/1/0Y
Y®0Z0/ Z/0V
Z®L/0 Z
V®0V1/1V
Can you convert G into CNF consider the new Grammar is G1.
Q4. Design TM for the function
assume (n,m>0), by drawing a transition diagram (Remember to identify the start state by an arrow and final state by double circles
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .