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

Detailed Intuition

---

beautifully explained!
I have a doubt , in 4th part, in case 1, when there is atleast one final state in DFA, how you can gurantee , you can reach it on epsilon move?

in question, δ2​(q00​,ϵ)={⟨q0​,q,q⟩ ∣ q∈Q}

it does not say that, on epsilon move, FOR EVERY q,  there is a transition from qoo ?? @0shan

it would be for some q, not every.

---

The confusion comes from interpreting the set notation.
The notation δ2​(q00​,ε)={⟨q0​,q,q⟩∣q∈Q}

already defines one ε-transition for every state q∈Q. It is not saying "there exists some q."
Rather, it lists all possible ε-successors.
The NFA is free to take any one of those transitions, and if one of them reaches an accepting state, the input is accepted. This is exactly the power of nondeterminism.

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

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

---

Soon ?

---

why is the answer to ii and iii question L U Suffix(L) and L U Prefix(L). Should it not be just Suffix(L) and Prefix(L)?

Anways suffix(L) and Prefix(L) also contains L , so doing L U Suffix(L) = Suffix(L) and similarly for Prefix(L)

 

Answer 2

My approach to the problem,

Answer 3

pardon me for poor writing :)

Comments

https://courses.grainger.illinois.edu/cs374/sp2019/lec_b/01_22_19.pdf        https://courses.grainger.illinois.edu/cs373/sp2010/lectures/lect_04.pdf      https://courses.grainger.illinois.edu/cs373/fa2013/Lectures/lec08.pdf

Answer 4

Detailed Intuition