The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+22 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.1k points)
edited by | 1k 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

+23 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.1k 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
49,830 questions
54,810 answers
80,885 users