CMI2023-A: 6

Question

Consider the automaton over the alphabet $\{a, b, c\}$ shown in Figure $1$. The initial state is the leftmost state. States with a double circle are accepting states.
 

What is the complement of the language accepted by this automaton?

• A. $\{\epsilon\}$
• B. $c^{*}+a^{*}+b^{*}$
• C. $(a+b)^{*}+(b+c)^{*}+(c+a)^{*}$
• D. None of the above

   

Answer 1

Question asking about complement of the language accepted by the given automata.

As string "abc" is not accepted by the given automata, then string must be member of complement of the language accepted by the automata.

A. {Epsilon} doesn't contain "abc" - this is not correct option.

B. c*+a*+b* - string "abc" can't generate by this Regular Expression- this is not correct option.

C. (a+b)*+(b+c)*+(c+a)*- string "abc" can't generate by this Regular Expression- this is not correct option.

Hence, Option D is correct.

 

What about correct Regular Expression ?

Whenever there is 3 different symbols involved in the string, then that string will be rejected by the Automata. So that will be in the complement of the language accepted by the Automata.

Note that those three different symbols may be in any order.

One possible R.E.= $\epsilon+((a^+.b^+.c^+)+(a^+.c^+.b^+)+(b^+.a^+.c^+)+(b^+.c^+.a^+)+(c^+.b^+.a^+)+(c^+.a^+.b^+)). (a+b+c)^*$

---

R.E of language accepted by given Automata is $(a+b)^++(b+c)^++(c+a)^+$