0

{w belongs to all string patterns as a^i b^j a^k | i+j=even and j+k =odd}

draw a DFA and find its regular language.

please note here, i have put comma in between the format of aba string just for easy understanding for all viewers.

what i have done so far is , the 2 possible condition should be 1) i=even, j=even, k=odd 2) or i=odd, j=odd, k=even

Can you tell me if b, ba, bba, bbbbbaba,aaaba are accepted or not??

xxx
  • 69

1 Answers1

0

OK, the regular language expression should be: (a(aa)*b(bb)*(aa)*)U((aa)*(bb)*a(aa)*) meaning, as you already stated: either the first block of a's and b's should each have an odd number, and the second block of a's should have an even number,
or the first block of a's and the b's should have an even number, and the second block of a's should have an odd number (a handy trick for getting k modulo n of some letter is the expression $a^k(a^n)^*$, here for an odd number of a's for example, we use the a(aa)* expression).

The automaton should look like this (accepting states marked with double circle):
automaton for the language above.

As to your question, it is easy to see (following the automaton) that bba is accepted, and the rest rejected.

Community
  • 1
Yotam D
  • 369
  • after the start, in the first a, how it went to the final state?? as in start a=even, b=even, c=even, in first a, a =odd, b=e,c=e. but this pattern we dont require. right?? – xxx Sep 25 '14 at 21:03
  • first block of a's has 0 a's, block of b's have 0 b's, and final block of a's have 1 (or other odd number) of a's. Or would we like to assume that i,j,k>0? in that case we should build another automaton. – Yotam D Sep 25 '14 at 21:05
  • initially it is even,even,even. now one a comes => odd, even even => not our desired combo – xxx Sep 25 '14 at 21:09
  • one more thing, i know it is correct but why?? starting from first, when b comes, then a comes, it goes to dead state why?? cant it be baaba ? – xxx Sep 25 '14 at 21:10
  • You can look at a as $ab^0a^0$, but the combo also implies a=$a^0b^0a$, which is even,even,odd - what we wanted. – Yotam D Sep 25 '14 at 21:11
  • The pattern you gave was $a^ib^ja^k$, and baaba is not in that pattern, since it has two blocks of b's separrated by 'aa'. Also, the reason that b,a leads to the "junk" state, is that after an even number (zero) of a's, and odd (one) number of b's, there must be another b, or else i+j=odd. – Yotam D Sep 25 '14 at 21:18