in Theory of Computation edited by
1,337 views
8 votes
8 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
1.3k views

4 Comments

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

1 Answer

2 votes
2 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

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.
0
0
edited by

@gatecse “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).

1
1

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

0
0

Related questions