Gate Bits FA and RE 5

In this class, We discuss Gate Bits FA and RE 5.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of finite automata and regular expressions. Click Here.

Example 1:

Gate 2007

Consider the following Finite State Automaton:

which regular expression gives the language accepted by this automaton?

(A) b∗ab∗ab∗ab∗

(B) (a+b)∗

(D) b∗ab∗ab∗

Answer: C

Check the finite automata to the regular expression state elimination method. Click Here.

We move to the final state from the finite automata by taking b*a.

After reaching the final state, the finite automata accept any set of input symbols.

Option C matches the regular expression.

Example 2:

Consider the automata given in the previous question. The minimum state automaton equivalent to the above FSA has many states.

(A) 1

(B) 2

(C) 3

(D) 4

Answer: B

Click Here to understand how to minimize the DFA.