August 10, 2023
August 11, 2023
August 10, 2023
###### GATE 2022
August 11, 2023
 Question 14
Consider the Deterministic Finite-state Automaton (DFA) A shown below. The DFA runs on the alphabet {0, 1}, and has the set of states {s, p, q, r}, with s being the start state and p being the only final state. Which one of the following regular expressions correctly describes the language accepted by A?
 A 1(0*11)* B 0(0 + 1)* C 1(0 + 11)* D 1(110*)*
Question 14 Explanation:
From the given DFA diagram, it clearly shows that there is no outgoing edge from node “r” so Regular expression won’t start with “0” , Option -B eliminated.
Starting state is “s” and Final state is “p”.
There are two outgoing edges from the state “p”.
one edge from state “p” to itself with alphabet “0” and another from State “p” to “q” and “q” to “p” with alphabet “1”
So most suitable answer is option C
Question 14 Explanation:
From the given DFA diagram, it clearly shows that there is no outgoing edge from node “r” so Regular expression won’t start with “0” , Option -B eliminated.
Starting state is “s” and Final state is “p”.
There are two outgoing edges from the state “p”.
one edge from state “p” to itself with alphabet “0” and another from State “p” to “q” and “q” to “p” with alphabet “1”
So most suitable answer is option C