The Gateway to Computer Science Excellence
+23 votes

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.2k points)
edited by | 1.2k views
what if the remaining input will stand or loop within the instead of giving b as back input let its loop there itself...............and same do for all????????

2 Answers

+24 votes
Best answer

DFA for A:


Part (B):

by Loyal (8.1k points)
edited by
How dfa A will accept baabbaab?? I think there should be transition from final stage to state 2???

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.9k points)
edited by
q3 will be final.

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

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,737 questions
57,333 answers
105,197 users