edited by
14,622 views
71 votes
71 votes

Consider the following finite automata $P$ and $Q$ over the alphabet $\{a, b, c\}$. The start states are indicated by a double arrow and final states are indicated by a double circle. Let the languages recognized by them be denoted by $L(P)$ and $L(Q)$ respectively.

The automation which recognizes the language $L(P) \cap L(Q)$ is :

edited by

6 Answers

Best answer
92 votes
92 votes

Design an automaton using $P$ and $Q$  having $p_0q_0$ as start state  

$\delta(p_0q_0,a) \rightarrow \delta(p_0,a) \cup \delta(q_0,a)$
$$\begin{array}{|l|l|l|l|}\hline \text{Q \ $\Sigma$}  &  \text{a} & \text{b} & \text{c} \\\hline  \text{$\rightarrow p_0q_0^*$}  &  \text{$p_1q_2$} & \text{$p_2q_1$} & \text{} \\\hline 
\text{$p_1q_2^*$}  &  \text{$p_3q_3$} & \text{} \\\hline \text{$p_2q_1^*$}  &  \text{$p_1q_2$} & \text{$p_3$ (No Need)} & \text{}\\\hline \text{$p_3q_3^*$}  &  \text{} & \text{$q_2$ (No Need)} & \text{$p_2q_1$} \\\hline \end{array}$$

In case of intersection final states are those where final states of P and final states of Q come together. 

"No need" in above table mean, when we reach to $p_3$ (or $q_2$) then we cannot reach to any final state because we cannot have states of $P$ and $Q$ together (intersection). Hence, this is not shown in diagram [may draw a dead state for it to make it a DFA (as noted at end) ]

Automaton results in:

That is option A .

Note : DFA must have transition for each symbol $Q \times \Sigma \rightarrow Q$ and hence our automaton is not a DFA as we do not have transitions to dead state.

edited by
62 votes
62 votes
See the languages being accepted by P and Q. In P before a 'c' there must be either 'b' or 'aa'. In Q, before 'c' there must be 'aa'. So, obviously, in their intersection before 'c' there must be 'aa' which is satisfied only by option A.
26 votes
26 votes

One string "aa" is common to both.
Which is accepted by only A not by any other machine. (Ans)

3 votes
3 votes
ans (A)...
Answer:

Related questions

42 votes
42 votes
7 answers
1
Ishrat Jahan asked Oct 30, 2014
7,776 views
Consider the regular expression $R = (a + b)^* (aa + bb) (a + b)^*$Which deterministic finite automaton accepts the language represented by the regular expression $R$?
47 votes
47 votes
4 answers
2