Register

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

• edited by
282 views
3 votes
3 votes

Which of the given options correctly represents the finite automaton given below?
(Mark all the appropriate choices)

 

  1. $\left(aa + bb + (ba + ab)(ab + ba)^{\ast}(aa + bb)\right)^{\ast}$
  2. $\left(aa + bb + (ba + ab)(aa + bb)^{\ast}(ab + ba)\right)^{\ast}$
  3. $\left(ab + ba + (ba + ab)(aa + bb)^{\ast}(ab + ba)\right)^{\ast}$
  4. $\left(bb + aa + (ab + ba)(bb + aa)^{\ast}(ba + ab)\right)^{\ast}$
• edited by
User Avatar

2 Answers

3 votes
3 votes

We can apply the state elimination method and get the regular expression.

  1. Initial state is not suppose to have any incoming edges.
  2. Final state is not suppose to have any outgoing edges.
  3. There should be only one final state.
  4. Eliminate all the remaining state other than the initial and final state in any order.

So, the correct answer is $B;D.$

• edited 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
4 votes
4 votes
2 answers
3
gatecse asked Sep 29, 2020
377 views
GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 5
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 = $_____
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 de...
User Avatar
2 votes
2 votes
1 answer
4
gatecse asked Sep 29, 2020
79 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!