1,340 views

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

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

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.

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

Is B really L union suffix(L)?
If we assume that “there are NO unreachable states” in the DFA $M$ then, Yes.

How to prove the language of suffixes of a regular language is still regular:

Given a DFA for $L$, let $Q$ be the set of states that are reachable from the start state. Construct an $NFA-ϵ$ by adding a new start state $S$ and adding an $ϵ-transition$ from $S$ to each state in $Q$. You can see the new $NFA-ϵ$ recognizes $suffix(L)$.

Page no 6 ( https://courses.engr.illinois.edu/cs373/sp2013/Lectures/lec08.pdf  )

https://cs.stackexchange.com/questions/120158/how-to-prove-the-language-of-suffixes-of-a-regular-language-is-still-regular

https://math.stackexchange.com/questions/304379/suffix-regular-language
Yes, that’s true. Actually the question is not very difficult. We have to trace the working based on $r$ in the tuple $\langle p,q,r \rangle$ which is simulating nothing but the DFA for L.
edited

“Best Answer” could have multiple definitions here but to convince a larger group of people, it is preferable to select answer as Best Answer which have a formal proof (if it demands).

@ankitgupta.1729 That problem comes only when we have such an answer. If only one answer is there it is anyway the “best answer”. And “best answer” is not a permanent thing – when better answer comes that can become the best answer.