Aspire's Library

A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET

Previous Year Question (PYQs)



A Turing Machine for the language
$L=a^n b^m c^n d^m \mid n \ge 1,\ m \ge 1$ is designed.

The resultant model is

$M=({q_0,q_1,q_2,q_3,q_4,q_5,q_6,q_7,q_f},{a,b,c,d},{a,b,c,d,X_1,X_2,Y_1,Y_2},\delta,q_0,B,{q_f})$

and part of $\delta$ is given in the transition table.

You need to write the following questions based on design of Turing Machine for the given language.

Note that, while designing the Turing Machine $X_1$ and $X_2$ are used to work with $a$'s and $c$'s and $Y_1$ and $Y_2$ are used to handle $b$'s and $d$'s of the given string.


What is the Move in the cell with number $M4$ of the resultant Table?






Solution

$M4$ is in state $q5$ on symbol $Y1$.

Here, $Y1$ represents a marked $b$.

After marking one corresponding $d$ as $Y2$, the machine moves left and reaches $Y1$.

Now it should move right and again go to state $q3$ to search for the next unmarked $b$.

Therefore,

$M4=(q3,Y1,R)$



Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More

Ask Your Question or Put Your Review.

loading...