GATE CSE 1988 | Question: 15

Question

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\}$

Comments

DFA 'M'

$M = (Q,\Sigma, \delta,q_0,F)$

Let, $Q = \{q_0,q_1\}, F= {q_1}$ and the transition function be defined as -

$\delta:$

$L = \{\sigma,\sigma_3,\sigma_5\ldots \}$ (odd number of $\sigma s$)

---

NFA $'M_2'$

$M_2 = (Q_2,\Sigma,\delta_2,q_{00},F_2)$

$Q_2 = \{q_{00}, $

• $\langle q_0,q_0,q_0 \rangle$
• $\langle q_0,q_0,q_1\rangle$
• $\langle q_0,q_1,q_0\rangle$
• $\langle q_0,q_1,q_1\rangle$
• $\langle q_1,q_0,q_0\rangle$
• $\langle q_1,q_0,q_1\rangle$
• $\langle q_1,q_1,q_0\rangle$
• $\langle q_1,q_1,q_1\rangle$}

Now, (A) $F_2 = A = \{\langle p,q,r \rangle\mid p \in F; q,r \in Q\} \forall p,q,r \in Q$ & $\sigma \in \Sigma$

Now NFA $M_2$ will be

$L' = \{\sigma,\sigma_3,\sigma_5\ldots \}$

so $L' = L$ so $M_2 \equiv M$

$\Rightarrow$ we can take other transition rules for $'M'$ like,

1. 
2. 

 etc or $Q= \{q_0,q_1,q_2\ldots \}$

In all cases, $L' = L$ because, we have to start with triplet $\langle q_0, , \rangle$ & then follow the path as in $'M'$ and first part of the triplet is important here because it shows the final state of NFA $'M_{2}’$ since $\Sigma = \{\sigma\}$ only, we have to trace first part of the triplet of $M_2$ which is same as tracing of DFA $'M'$.

---

I guess the final states in the NFA M² are misnamed. Maybe the first elements of the triplets should be q¹. ??

---

Yes. Also, I can see, triplet <q0, q1,q1> is repeated also.

This question was edited previously. Initially, there was an image added by me. It is difficult to say, this mistake is due to editing or this mistake was from my side.

Anyway, I am converting this answer to a comment because initially, it was a comment and also it is incomplete.

Edit: "This question was edited previously." - Here, I have written "question" by mistake. It is "Answer" i.e. "This answer was edited previously."

---

@ankitgupta.1729 You can see edit history for the question here and for the answer here. Is anything done wrong? Please do not convert answers to comments – because they are not “comments”

---

@Arjun sir, I have written “Question” instead of “Answer” by mistake above. Initially, I have checked the edit history for this answer.

I still remember, Initially I have added an image in the form of comment but it was converted to an answer and then image was removed from the answer.

It was comment because this is not an answer. It is just an attempt to this question and it was incomplete also. So, I had added it as a comment.  

---

Is this the one?

---

An answer need not be "perfect" to be an answer. It can also be a work in progress with suitable wordings.

---

Yes, It is the same image which I had added initially.

If you wish, you can convert that comment to answer again :P

I agree with you that answers need not be perfect. If some wordings or explanations were missing, I had not converted it into a comment. But, here, except first part, it does not answer rest of the parts and I don’t prefer to write things in the “Answer” section, if it does not answer all parts of the question.

---

https://gateoverflow.in/94642/gate-cse-1988-question-15?show=382950#a382950 

---

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

---

Am i the only one who doesn’t get it even after checking the solution.

Answer 1

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.$

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.

---

@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. 

---

@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. 

Answer 2

pardon me for poor writing :)