Register

GO Classes DPP | TOC|FA

495 views
5 5 votes

Consider a Deterministic Finite Automaton (DFA) defined as follows:

  • States $(Q):\left\{q_0, q_1, q_2, q_3, q_4\right\}$
     
  • Alphabet ( $\Sigma$ ): $\{a, b\}$
     
  • Start State: $q_0$
     
  • Final States $(F):\left\{q_1, q_2\right\}$
     
  • Transition Function ( $\delta$ ):

         | Current State | Input 'a' | Input 'b' |

$$
\begin{aligned}
& |:--|:--|:---| \\
& \left|\rightarrow q_0\right| q_1\left|q_2\right| \\
& \left|* q_1\right| q_1\left|q_3\right| \\
& \left|* q_2\right| q_4\left|q_2\right| \\
& \left|q_3\right| q_1\left|q_3\right| \\
& \left|q_4\right| q_4\left|q_2\right|
\end{aligned}
$$

(The arrow $\rightarrow$ indicates the start state, and the asterisk indicates a final state.)
The language recognized by this machine is:

  1. The set of all non-empty strings that start and end with the same symbol.
     
  2. The set of all non-empty strings that start and end with different symbols.
     
  3. The set of all strings that contain the substring aa or bb .
     
  4. The set of all strings where the total number of symbols is odd.

4 Answers

2 2 votes

Option A  is correct.

Given DFA is -

Option B is incorrect as - Strings starting and ending with same symbol are accepted.

Option C is incorrect as - The string 'abb' should be recognised as per the option but the dfa does not accept it.

Option D is incorrect as - The string "abba" is accepted but number of symbols is even.

0 0 votes
Option A  is correct

Option B is incorrect as - Strings starting and ending with same symbol are accepted.

Option C is incorrect as - The string 'abb' should be recognised as per the option but the dfa does not accept it.

Option D is incorrect as - The string "abba" is accepted but number of symbols is even.
Voting & Accepting an answer helps improve the community
Answer:
← Previous · web UI and searching...Next → · GO Classes DPP | TOC...
← Previous in category · geeks websiteNext in category → · GO Classes DPP | TOC...
Position:
Show:

Related questions

7 7 votes
2 2 answers
322
322 views
GO Classes asked Oct 8, 2025
322 views
GO Classes DPP | TOC | RE
If the regular set $\mathbf{A}$ is represented by $A=(b+a b)^*(a+\epsilon)$ and the regular set $\mathbf{B}$ is represented by $B=\left(b^* a b^*\right)^*(a+\epsilon)$, w...
5 5 votes
3 3 answers
392
392 views
GO Classes asked Oct 8, 2025
392 views
GO Classes DPP | TOC | RE
The string 'babaa' does not belong to the set represented by$\left(a^* b\right)^*(a+b)$ $b\left(a^* b^*\right)^* a$ $b\left(a+b^* a\right)^*$ $\left(b^* a\right)^*\left(a...
3 3 votes
3 3 answers
347
347 views
GO Classes asked Oct 8, 2025
347 views
GO Classes DPP | TOC | RE
Which two of the following four regular expressions are equivalent over the alphabet $\{a, b\}$ ? ( $\epsilon$ is the empty string).i. $(a+b)^*$ii. $a^*\left(b a^*\right)...
2 2 votes
1 1 answer
302
302 views
GO Classes asked Oct 8, 2025
302 views
GO Classes DPP | TOC|MEALY MACHINE
A finite state machine is represented by the diagram below. It has two states, $Q_{\text {even }}$ (the start state) and $Q_{\text {odd }}$. The machine takes a binary st...