CODEWITHSUNDEEP
regexregular-languagefinite-automatadfa
Khurram Ali
Khurram Ali

Reputation: 1679

Regular expression for "even odd language of strings over {a, b}

I want to make regular expression having even number of b's and odd number of a's also DFA AND NFA of it for this i made below DFA

I got these two Regular Expression

  1. Regular Expression For Even no of b's (a*a*a*bb)*

  2. Regular Expression For Odd no of a's (a b*b*)(a b*b*a)*

QUESTION: Did I make the right DFA ?

Edits: I got DFA From Grijesh Chauhan Answer still unable to make regular expression which will allow only even number of b's and odd nubmer of a's . I also tried this Regular Expression

(a(bb)*(aa)*)*

Note: From above RE only those strings are generated which start from a but i want that RE which generate string of even number of b's and odd number of a's regardles of starting from a or b

enter image description here

Upvotes: 1

Views: 10022

Answers (3)

Divyesh Jesadiya
Divyesh Jesadiya

Reputation: 957

use this DFA....may be help you....i made in paint so,not looking pretty...enter image description here

Upvotes: 0

Taemyr
Taemyr

Reputation: 3437

Your DFA is incorrect. One can see this because you have cycles of odd length. Following those cycles changes the even/odd parity. So I can start with "babb" which your DFA accepts, having odd number of b's and odd number of a's. q0->q1->q2 is a cycle of 3 a's so adding 3 a's when I am in one of those states does not change wether the automata accepts, so your automata accepts "aaababb" despite neither having an odd number of a's or an even number of b's. (Also your machine fails for "bab", despite this having both odd number of a's and even number of b's)

Your DFA should at minimum keep track of the parity of the number of a's and b's. So you should start with 4 states. Q_{even,even},Q_{even,odd},Q_{odd,even} and Q_{odd,odd}. Having labeled the states in this way it should be straightforward to set up the transitions and selecting what should be the intial and accepting states.

Your regular expressions also has some issues. I would note that a* means 0 or more a's, so a*a* means 0 or more a's followed by 0 or more a's. This means that a*a*=a*. Other than that see Georg's answer.

Conventional definitions are such that every DFA is also a NFA. Converting can be a problem when going from NFA to DFA.

See Need Regular Expression for Finite Automata: Even number of 1s and Even number of 0s for a discussion on what algebra can be done on regular expressions.

Upvotes: 2

Georg
Georg

Reputation: 5781

The regexes are incorrect. They should be

  • a*(ba*ba*)* for an even number of b
  • b*ab*(ab*ab*)* for an odd number of a

There is a systematic way to perform a merge of these two, because every regular expression can be represented by a state machine and vice versa and there is definitely a way to merge state machines such that the resulting state machine accepts if either of the two state machines accept, but I cannot remember how this is done directly on regular expressions.

Upvotes: 2

Related Questions