The Gateway to Computer Science Excellence
+22 votes
1.1k 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 by Veteran (52.1k points)
edited by | 1.1k 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

+23 votes
Best answer

DFA for A:

 

Part (B):

by Loyal (8.1k points)
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)

by Boss (41.4k points)
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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,164 answers
193,778 comments
93,865 users