search
Log In
23 votes
1.6k views

Construct DFA's for the following languages:

  1. $L=\left\{w \mid w \in \{a,b\}^*, \text{ w has baab as a substring } \right\}$
  2. $L=\left\{w \mid w \in \{a,b\}^*,  \text{ w has an odd number of a's and an odd number of b's } \right\} $
in Theory of Computation
edited by
1.6k views
1
what if the remaining input will stand or loop within the state....................ie instead of giving b as back input let its loop there itself...............and same do for all????????

2 Answers

26 votes
 
Best answer

DFA for A:

 

Part (B):


edited by
0
How dfa A will accept baabbaab?? I think there should be transition from final stage to state 2???
0
@vupadhayayx86

Observe, after "baab" , there is a loop (a+b)*, so after once "baab" occurred, it will accept anything. so yout string "baabbaab" will definitely be accepted.
16 votes

DFA for (B)


edited by
1
q3 will be final.

q1 is for odd no of a's and even no of b's as it accepting a, bba, etc.
0
Updated.

Related questions

20 votes
4 answers
1
6k views
Given an arbitrary non-deterministic finite automaton (NFA) with $N$ states, the maximum number of states in an equivalent minimized DFA at least $N^2$ $2^N$ $2N$ $N!$
asked Sep 14, 2014 in Theory of Computation Kathleen 6k views
23 votes
2 answers
2
1.7k views
Let a decision problem $X$ be defined as follows: $X$: Given a Turing machine $M$ over $\Sigma$ and any word $w \in \Sigma$, does $M$ loop forever on $w$? You may assume that the halting problem of Turing machine is undecidable but partially decidable. Show that $X$ is undecidable Show that $X$ is not even partially decidable
asked Sep 15, 2014 in Theory of Computation Kathleen 1.7k views
20 votes
2 answers
3
4.1k views
Which of the following statements is true? If a language is context free it can always be accepted by a deterministic push-down automaton The union of two context free languages is context free The intersection of two context free languages is a context free The complement of a context free language is a context free
asked Sep 14, 2014 in Theory of Computation Kathleen 4.1k views
25 votes
4 answers
4
7.1k views
Consider a DFA over $\Sigma=\{a,b\}$ accepting all strings which have number of a's divisible by $6$ and number of $b$'s divisible by $8$. What is the minimum number of states that the DFA will have? $8$ $14$ $15$ $48$
asked Sep 14, 2014 in Theory of Computation Kathleen 7.1k views
...