Original Question

GATE CSE 1990 Question 3(ii):

Consider the following finite automaton:

    a
  ↗   ↘
→(q0)  (q1)
  ↖   ↙ ↘
    b    a
        (q2)
         ↺
         a

What is the language accepted by this automaton?

Detailed Solution

To determine the language accepted by this finite automaton, let’s analyze its structure and behavior:

1. State Analysis

   • Initial state: q0
   • Final state: q2
   • Intermediate state: q1

2. Transition Analysis

   • From q0:
     • ‘a’ leads to q1
     • ‘b’ loops back to q0
   • From q1:
     • ‘a’ leads to q2 (final state)
     • ‘b’ goes back to q0
   • From q2:
     • ‘a’ loops in q2
     • No transition for ‘b’

3. Language Pattern

   To reach the final state q2, we need:

   • Any number of ‘b’s followed by ‘a’ to reach q1
   • Another ‘a’ to reach q2
   • Any number of ‘a’s (including zero) after reaching q2

4. Regular Expression

   The language can be described by the regular expression:

   L = b*aa*

Therefore, the automaton accepts strings that consist of zero or more ‘b’s, followed by exactly two ‘a’s, and then zero or more additional ‘a’s.

Summary

The finite automaton accepts the language L = b*aa*. This means:

• The string must contain at least two ‘a’s.
• Any number of ‘b’s (including zero) can appear before the first ‘a’.
• After the first two ‘a’s, only additional ‘a’s are allowed (including zero additional ‘a’s).
• No ‘b’ can appear after the first ‘a’ in an accepted string.

Potential Student Doubts

1. Why can’t there be ‘b’s after ‘aa’?

   Once the automaton reaches state q2, there’s no transition for ‘b’. Any ‘b’ after reaching q2 would lead to a dead state, making the string unacceptable.

2. Is ‘aa’ the shortest accepted string?

   Yes, ‘aa’ is the shortest string accepted by this automaton. It’s the minimum required to reach the final state q2.

3. Can the string have only ‘b’s?

   No, a string with only ‘b’s will never reach the final state q2. At least two ‘a’s are required for acceptance.

Additional Study Material

To further understand finite automata and regular languages, consider studying:

• Deterministic vs Non-deterministic Finite Automata (DFA vs NFA)
• Conversion between regular expressions and finite automata
• Closure properties of regular languages
• Pumping lemma for regular languages
• Minimization of DFAs
• Applications of finite automata in lexical analysis and pattern matching