edited by
2,835 views
10 votes
10 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\}$

edited by

2 Answers

Best answer
4 votes
4 votes
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

Related questions

19 votes
19 votes
2 answers
1
go_editor asked Dec 18, 2016
2,883 views
What is the type of the language $L$, where $L=\{a^n b^n \mid 0 < n < 327 \text{-th prime number} \}$
8 votes
8 votes
2 answers
2