GATE CSE 2005 | Question: 53

Question

Consider the machine $M$:

The language recognized by $M$ is:

• A. $\left\{ w \in \{a, b\}^* \text{ | every a in $w$ is followed by exactly two $b$’s} \right\}$

• B. $\left\{w \in \{a, b\}^* \text{ | every a in $w$ is followed by at least two $b$’s} \right\}$

• C. $\left\{w \in \{a, b\}^* \text{ | $w$ contains the substring ‘$abb$’} \right\}$

• D. $\left\{w \in \{a, b\}^* \text{ | $w$ does not contain ‘$aa$’ as a substring} \right\}$

Comments

@Vikrant: b is the answer assuming start start state is also accepting rt? I guess it was a printing mistake.

---

It should be aa not just a

---

Key point-> For the string which is like contain there is no Dead state only final state will be there.

so C is wrong.

Answer 1

many might get confuse in option D. Option D is wrong because it is specified the the language does not contain “aa” as substring, means the string containing aa will only be not accepted, bt the strings abba is also not accepted (which is not specified in the language).

Answer 2

therefore option A,C,D can be discarded

so option B is correct