in Theory of Computation edited by
1,340 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

5 Comments

Is B really L union suffix(L)?
0
0
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
0
0
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