search
Log In
1 vote
1.9k views

Given a Turing Machine

$M=(\{q_0, q_1, q_2, q_3\}, \{a,b\}, \{a, b, B\}, \delta, B, \{q_3\})$

where $\delta$ is a atransaction function defined as

$\delta(q_0,a)=(q_1, a, R)$

$\delta(q_1, b)=(q_2, b, R)$

$\delta(q_2, a)=(q_2, a, R)$

$\delta(q_2,b)=(q_3, b, R)$

The language L(M) accepted by the Turing machine is given as:

  1. aa*b
  2. abab
  3. aba*b
  4. aba*
in Theory of Computation
recategorized by
1.9k views

3 Answers

5 votes
 
Best answer
Turing machine head movement only right direction...

We can build dfa for it..

Total 4 states are given ...

(q0,a) gives q1 no transition for b

(q1,b) gives q2 no transition for a

That means string start with ab

Now ..(q2,a) gives q2 that means it is loop on q2...

From (q2,b) go to q3 and after that no transition... That means string end with" b"

So C. Is right ans.

selected by
2 votes

C is Ans.

Whenever all the states in TM are  Right Or Left @ time it works like DFA.

So here it is DFA like below fig.


edited by
0 votes

According to given question, we have transtion:
δ(q0, a) = (q1, a, R)
δ(q1, b) = (q2, b, R)
δ(q2, a) = (q2, a, R)
δ(q3, b) = (q3, b, R)
We can draw a DFA:
57
Language will be aba*b.
So, option (C) is correct.

Related questions

3 votes
4 answers
1
3.5k views
Let L be the language generated by regular expression 0*10* and accepted by the deterministic finite automata M. Consider the relation $R_M$ defined by M as all states that are reachable from the start state. $R_M$ has ___ equivalence classes. 2 4 5 6
asked Aug 20, 2016 in Theory of Computation jothee 3.5k views
1 vote
1 answer
2
1.1k views
The symmetric differences of two sets $S_1$ and $S_2$ is defined as: $S_1 \oplus S_2 =\{x \mid x \in S_1 \text{ or } x \in S_2, \text{ but x is not in both } S_1 \text{ and } S_2 \}$ The nor of two languages is ... difference The family of regular languages are closed under both symmetric difference and nor The family of regular languages are not closed under both symmetric difference and nor
asked Aug 20, 2016 in Theory of Computation jothee 1.1k views
4 votes
3 answers
3
2k views
The regular expression for the complement of the language $L=\{a^nb^m \mid n \geq 4, m \leq 3\}$ is: $(\lambda +a+aa+aaa)b^*+a^*bbbb^*+(a+b)^*ba(a+b)^*$ $(\lambda +a+aa+aaa)b^*+a^*bbbbb^*+(a+b)^*ab(a+b)^*$ $(\lambda +a+aa+aaa)+a^*bbbbb^*+(a+b)^*ab(a+b)^*$ $(\lambda +a+aa+aaa)b^*+a^*bbbbb^*+(a+b)^*ba(a+b)^*$
asked Jul 11, 2016 in Theory of Computation Sanjay Sharma 2k views
3 votes
1 answer
4
906 views
Consider the following two languages: $L_1=\{0^i1^j \mid ged (i,j)=1 \}$ $L_2$ is any subset of 0* Which of the following is correct? $L_1$ is regular and $L_2*$ is not regular $L_1$ is not regular and $L_2*$ is regular Both $L_1$ and $L_2*$ are regular languages Both $L_1$ and $L_2*$ are not regular languages
asked Jul 11, 2016 in Theory of Computation Sanjay Sharma 906 views
...