The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+19 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\} $
asked in Theory of Computation by Veteran (52k points)
edited by | 954 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):

answered 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)

answered by Boss (41k 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,541 questions
54,083 answers
70,992 users