in Theory of Computation edited by
2,797 views
10 votes
10 votes

Consider the DFA  $M$ and NFA  $M_{2}$  as defined below. Let the language accepted by machine $M$ be $L$. What language machine $M_{2}$ accepts, if

  1. $F2=A?$
  2. $F2=B?$
  3. $F2=C?$
  4. $F2=D?$
  • $M=(Q, \Sigma, \delta, q_0, F)$
  • $M_{2}=(Q2, \Sigma, \delta_2, q_{00}, F2)$

Where,

$Q2=(Q \times Q \times Q) \cup \{ q_{00} \}$

$\delta_2 (q_{00}, \epsilon) = \{ \langle q_0, q, q \rangle \mid q \in Q\}$

$\delta_2 ( \langle p, q, r \rangle, \sigma ) = \langle \delta  (p, \sigma), \delta (q, \sigma), r \rangle$

for all $p, q, r \in Q$ and $\sigma \: \in \: \Sigma$

$A=\{ \langle p, q, r \rangle \mid p \in F; q, r \in Q \}$

$B=\{\langle p, q, r \rangle \mid q \in F; p, r \in Q\}$

$C=\{\langle p, q, r \rangle \mid p, q, r \in Q; \exists s \in \Sigma^*,  \delta (p,s) \in F \}$

$D=\{\langle p, q, r \rangle \mid p,q \in Q; r \in F\}$

in Theory of Computation edited by
2.8k views

4 Comments

very well explained but sir final states in M2 is different than what I am getting. like states are same but order in triplet is different
0
0
Am i the only one who doesn’t get it even after checking the solution.
1
1

2 Answers

4 votes
4 votes
Best answer
To solve this question, we must first understand “Idea behind Product Automata” which is “parallel computation”.

Also, we need to understand how to create DFA for $\text{PREFIX}(L), \text{SUFFIX}(L)$ if a DFA of $L$ is given.

Now, the answers:

1.  If $F_2 = A$ then $L(M_2) = L$

2.  If $F_2 = B$ then $L(M_2) = L \cup \text{SUFFIX}(L)$

3.  If $F_2 = C$ then $L(M_2) = L \cup \text{PREFIX}(L)$

4. If $F_2 = D$ then $L(M_2) = \Sigma^*$ if $F \neq \phi$, else $L(M_2) = \phi.$
selected by

4 Comments

@gatecse

If a question has one answer does not mean that it should be the best, if it is proved that it is correct then it might be the best though it is very difficult to define the answer as "best". The idea of "Useful Answer" is always good.

Since you have accepted the answer, so how do you know that this answer is correct without having a proof. This might or might not be correct and if it is correct then it can be proven with some investment of time but why it was quickly accepted as the best answer which is not having a proof because you feel so, right ?

In question, it is mentioned that $Q2 =  (Q \times Q \times Q) \cup \{q_{00}\}$, is it defined here what is the meaning of a union of a tuple and a set ?  

Theory of Computation is a mathematical subject and proofs, precise definitions, notations, assumptions all these things are very necessary to convince someone that something is correct. 
suppose, someone asks, what is the value of $1+2+3+...$ then some might say $\frac{-1}{12}$ (how a negative number for the sum of positive numbers ?) and some might say infinity and some might say some other values. So, to convince everyone, we need a proof to justify so that we can say this answer is correct or more than one answers can be correct based on the assumption we have taken.

If someone asks you what is the value of $\frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} +...$ and someone says $\frac{\pi^2}{6}$, though it is correct but to convince everyone, we need a formal proof or some reasoning (intuition might be wrong) to show that this is correct and additionally, we can also give some informal way to explain how $\pi$ comes into the picture. Writing all these things might make an answer "best", not only writing $\frac{\pi^2}{6}$. Eliminating options, intuition all these things are good for exams to solve questions quickly but writing proofs (or mentioning some links of the proof) make an answer beautiful and they might be the candidate for the best answer.

1
1

@ankitgupta.1729

Do you find any mistake in the given answer? If yes, please tell me, I will check if it is truly a mistake or not, and correct it if it is.

I didn’t have time to write the proof, I will write it soon. Without proving, I don’t write answers.

The proof of this answer will be added soon. 

1
1

@Deepak Poonia

I know you can write the proof and most of your answers are very good and well-explained. And, if I or anyone will invest some time on it, can prove it. Without proof, no one can say whether it is correct or not. 

My concern is not with you. I appreciate that you have written an answer for the question but my concern was with the selection of the answer which I have already mentioned above. 

0
0
1 vote
1 vote

pardon me for poor writing :)

Related questions