1

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 ?

  • How to merge above two Regular Expressions into one if both are correct??
  • How to Convert DFA into NFA?

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

Khurram Ali
  • 1,659
  • 4
  • 20
  • 37
  • 1
    This does not make much sense; `bab` has an even number of `b`s but does not match your first RE, `b` has an odd number of `b`s but does not match your second RE, `X*X*` = `X*` for all X, and all DFAs are already NFAs so I don't understand what you are trying to convert. There are also multiple ways to “merge” RAs; which way did you mean? Concatenation? – Dour High Arch Apr 28 '15 at 02:21
  • 1
    check this answer [Need Regular Expression for Finite Automata: Even number of `1`s and Even number of `0`s]()(http://stackoverflow.com/questions/17420332/need-regular-expression-for-finite-automata-even-number-of-1s-and-even-number-o/17434694#17434694) re-write solution with final state is Q2. -- it is duplicate actually – Grijesh Chauhan Apr 28 '15 at 06:38
  • @GrijeshChauhan i am looking for Regular Expresson ,DFA and NFA for even number of b's and odd number of a's – Khurram Ali Apr 28 '15 at 07:01
  • 1
    @KhurramAli yes the link answers your question, read I have given meaning of each state "Q1: Odd number of a and even number of b", accordingly you have to drive regex as I have written for "even a and even b". Give it a Try. – Grijesh Chauhan Apr 28 '15 at 07:17
  • @GrijeshChauhan Is '+' in the linked answer '|' in PCRE? – Taemyr Apr 28 '15 at 08:43
  • This is a question for http://cs.stackexchange.com/. Furthermore this is not a community to do your homework for you ... – Markus Apr 28 '15 at 08:53
  • @Taemyr Yes, In formal language for OR operator we use binary `+` (in regex in programming language we use `|` ) In programming languages `+` as unary operator uses for closure (for one of more times ) In formal languages for closure we write + in superscript [read: + Operator in Regular Expression](http://stackoverflow.com/questions/14122755/what-will-be-the-dfa-for-the-regular-expression-00101011/14123662#14123662) – Grijesh Chauhan Apr 28 '15 at 09:01
  • @GrijeshChauhan What would be the Regular Expression of State `Q1` which accepts even number's of b and odd number's of a ? – Khurram Ali Apr 28 '15 at 21:32
  • @KhurramAli you should read and understand how did I simplified those questions. and then similarly drive regular expression for state Q1 – Grijesh Chauhan Apr 29 '15 at 02:43

3 Answers3

2

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.

Georg
  • 5,626
  • 1
  • 23
  • 44
  • The second regexp should be for an odd number of a's. – Taemyr Apr 28 '15 at 08:24
  • @Taemyr No. In fact, in both regexes `a` only occurs as `a*` so that absolutely no statement can be made upon the number of `a`s. – Georg Apr 28 '15 at 08:30
  • I think you misunderstood what I meant. a's and b's should be switched in your second regexp because OP asks for odd number of a's. – Taemyr Apr 28 '15 at 08:35
2

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.

Community
  • 1
  • 1
Taemyr
  • 3,407
  • 16
  • 26
0

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

Divyesh Jesadiya
  • 1,105
  • 4
  • 30
  • 68