GATE IT 2007 | Question: 50

Question

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 :

• A.
• B.
• C.
• D.

Comments

Easy to solve using the hit-and-trial method.

Try to create a string that is accepted by both automata and contains all the alphabets.

For example:

• abaac → Both automata accept it, and only option A accepts it.

Therefore, the answer is A.

---

yes for me the counter example is : "aa"

---

Option A is correct

Just use product autometa it will very easy make and start state is P0Q0 and make fina states where both are in  final states.

Answer 1

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.

Comments

A simple solution to this question is that both automata of question accept string ‘aa’ but none of the options other A accept(others reject it) so, option A is correct answer.

---

P is not accepting string "abc"

But option A is accepting

It. as we need intersection so abc has not  to be accepted in answer

Am I wrong?

---

@Aky2000 abc is not accepted by A 

Answer 2

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.

Comments

edit : In P before a 'c' there must be either 'bb' or 'aa'

---

@mohan  In P before a 'c' there must be either 'b' or 'aa' because in string “bbcbc” before last c there is only b, not bb.

---

In P before c it is either b or a

Answer 3

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

Comments

easiest among all answer.

---

string aa is not accepted by option (a) so answer will be option (e) none of the above.

---

@gdas Recheck your observation.

Answer 4

ans (A)...

Comments

did you use any method or just brute force

---

Ya.. it's  brute force.. I knockout the options.. I taken string which is accepted by options then that should also be accepted by the two given automata.. I could found strings for the three but not for 1st one...

---

Is there any other way to solve this ques? Brute force is time consuming ...

---

don't you think brute force is risky as we may end up missing up a few strings and land upon an incorrect option?

---

What is mean by brute force method here ???

---

Trying random strings and check whether it satifies the option or not.

Answer 5

Another method for finding intersection is utilizing this property: L1 ∩ L2 = (L1' U L2')'

Now both the DFAs can be complemented (easy as only the set of final and non final states has to be changed), and then union can be applied (adding an initial state and then giving epsilon transitions from this state to both the previous initial states). However, this will give e-NFA which cannot be complemented directly. So we need to reduce it to a DFA and then complement it, to finally get L1 ∩ L2. This method may seem a little long but the only time consuming part is e-NFA to DFA conversion and if this part is simple for a given question then this method can also be used to find the intersection.

[Not giving an answer to this question because it has already been given. My aim was just to share this alternate method.]

Answer 6

i checked "aac ", it worked, every  wrong option got  eliminated
("aac" is common in both )

hence A.😎

Comments

I just thought about only one thing, what happens when we give 'aa' as input. both p and q accepts it but option b c d doesn't accept it. so option a is the answer. Hope its useful @Arjun sir