Skip to content
GATEiit

GATE CSE 2022 Q12: Regular expression for a three-state finite automaton

Question

Which one of the following regular expressions correctly represents the language of the finite automaton given below?

Finite automaton with a non-accepting start state; on a it goes to an accepting state that loops on b and returns on b; on b it goes to another accepting state that loops on a and returns on a
Tap the figure to enlarge

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 1/3 mark in GATE.
Show answer and explanation

Answer: D (official GATE 2022 final answer key)

Concept used: State elimination: loops through the start state, followed by a final excursion to an accepting state.

First step: Each round trip from the start state is ab∗bab^*b or ba∗aba^*a; the string must end in an accepting state, i.e. with ab∗ab^* or ba∗ba^*.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2022 CS question paper and final answer key, organised by IIT Kharagpur. Question paper · Answer key

More Theory of Computation PYQs

PracticePractise Theory of Computation questions →Full paperAll GATE CSE 2022 questions →