Register

GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 5

376 views
4 votes
4 votes
For $L=\{\varepsilon \},$ if the number of total and final states required in the minimal state deterministic finite automata to accept $L$ over $\Sigma = \{a,b\}$ are denoted by $a$ and $b$ respectively, then $a-b = $_____
User Avatar

2 Answers

Best answer
4 votes
4 votes
We need one initial state which is also the final state and one additional dead state. So, $2-1=1.$

So, the correct answer is $1.$
• selected by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2 votes
2 votes
1 answer
2
gatecse asked Sep 29, 2020
166 views
GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 13
Given that $\Sigma = \{a\},$ which of the following finite automata correctly implements the regular expression $a^{\ast}?$ (Mark all the correct options)
Given that $\Sigma = \{a\},$ which of the following finite automata correctly implements the regular expression $a^{\ast}?$ (Mark all the correct options)
User Avatar
2 votes
2 votes
1 answer
4
gatecse asked Sep 29, 2020
78 views
GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 20
Which of the following strings is a member of the language over $\{a, b\}$ defined by the regular expression $(aa + ab)^*(bb)^*$ ? $abbbba$ $abaabb$ $babbaa$ $bbaa$
Which of the following strings is a member of the language over $\{a, b\}$ defined by the regular expression $(aa + ab)^*(bb)^*$ ?$abbbba$ $abaabb$$babbaa$$bbaa$
User Avatar
Link Copied!