Register

GO Classes Test Series 2023 | Theory of Computation | Test 1 | Question: 16

• retagged by
341 views
2 votes
2 votes

For the deterministic finite automaton $M$ with state set $\{0,1,2\}$, alphabet of input symbols $\{a, b\}$, initial state $0 ,$ accepting states 1 and 2 , and next-state function
$$(0, a) \mapsto 2, \quad(1, a) \mapsto 1, \quad(2, a) \mapsto 0,\\
(0, b) \mapsto 1, \quad(1, b) \mapsto 0, \quad(2, b) \mapsto 2$$.
Which of the following is correct regular expression $r$ such that $\mathrm{L}(\mathrm{M})=\mathrm{L}(\mathrm{r})$ :

  1. $b a^{\ast }+a b^{\ast }$
  2. $\left(b a^{\ast } b+a b^{\ast } a\right)^{\ast }(b+a)$
  3. $\left(b a^{\ast } b+a b^{\ast } a\right)^{\ast }\left(b a^{\ast }+a b^{\ast }\right)$
  4. None of the above
• retagged by
User Avatar

2 Answers

4 votes
4 votes
Construct the DFA diagram and the set of strings that come to state $0$ is $\left(b a^{\ast } b+a b^{\ast } a\right)^{\ast }$ and then we have the final regular expression as union of regular expression corresponding to state $1$ and $2$ which is $\left(b a^{\ast } b+a b^{\ast } a\right)^{\ast }\left(b a^{\ast }+a b^{\ast }\right)$
User Avatar
2 votes
2 votes

just draw like this from question itself , no need for Arden’s theorem,it’s quite complex method….

 

User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

481
views
1 answers
3 votes
GO Classes asked Jun 9, 2022
481 views
GO Classes Test Series 2023 | Theory of Computation | Test 1 | Question: 25
Let $L$ be a language over an alphabet $\Sigma$. The equivalence relation $\sim_{L}$ on the set $\Sigma^{\ast }$ of finite strings over $\Sigma$ is defined by ... $\sim_{L}$-equivalence classes for this $L$ is ________
User Avatar
290
views
1 answers
3 votes
GO Classes asked Jun 9, 2022
290 views
GO Classes Test Series 2023 | Theory of Computation | Test 1 | Question: 18
Consider the following languages:The language of regular expression $(0+1)^{\ast } 11(0+1)^{\ast }$ ... $1=2$Neither $1$ is subset of $2$, nor $2$ is subset of $1$.
User Avatar
581
views
2 answers
4 votes
GO Classes asked Jun 9, 2022
581 views
GO Classes Test Series 2023 | Theory of Computation | Test 1 | Question: 14
Let $L$ be the language accepted by the following non-deterministic finite automaton with $\epsilon$-transitions:The number of states in the minimal DFA that accepts the ... is recognized by the above NFA over alphabet $\{a\},$ is ________
User Avatar
765
views
1 answers
3 votes
GO Classes asked Jun 9, 2022
765 views
GO Classes Test Series 2023 | Theory of Computation | Test 1 | Question: 22
Let $L$ be a language over an alphabet $\Sigma$. The equivalence relation $\sim_{\mathrm{L}}$ on the set $\Sigma^{\ast }$ of finite strings over $\Sigma$ ... $1$Only $2$BothNone
User Avatar
Link Copied!