The Gateway to Computer Science Excellence
+2 votes
2.1k views
The language given is $\text{$L = \{ w | w $ contains an equal no of occurrences of substrings '$ab'$ and $'ba' \}.$ }$ $L$ is regular $?$

Note$:-$   $aba ∈ L $since $'aba'$ contains $1$ occurrence of $'ab'$ and $1$ occurrence of $'ba'$ but $ abab ∉ L$
in Theory of Computation by Active (4.9k points)
edited by | 2.1k views
+1
It is regular

3 Answers

+7 votes
Best answer

Yes it is regular ..The reason being we have equivalent regular expression for it..The regular expression for the given language is given by :

(a+ b* a+) *  + (b+ a* b+)* 

Hence we can have equivalent NFA and DFA also..

Thus the given langauge is regular

by Veteran (102k points)
selected by
0
What is 1 and 0 here?

if 0 contains one extra ab?
0
Typo..:) Corrected..
+3

Does above regular expression include, L = ababba  ??

I think, It should be - R(L) = ∈ + a( a* + b+a+ )* + b( b* + a+b)*.

Please check..

+2
good point vijay
+1

I agree with u @vijaycs..

Actually my source was : http://www.cs.gordon.edu/courses/cps220/Notes/nonregular_languages

0
@vijaycs SIR,  in ababba   
Number of occurance of  ab  : 2
Number of occurance of ba : 1
BUt question is asked for equal number of occurance of ab and ba...

Correct me If wrong...
+1
No there are 2 occurence of ba , see the 2nd and 3rd characters pair and 5th and last characters of the string "ababba"..
+1

Ohh nice..  It should also accept jumbled character set also ?

aba  aba  

0
^Yes, you got it right . (y) @gokou sir :)
+2

@Habib, I think, The equiv. DFA is correct in your source ..please check it @Habib,  @srestha ?

+1
Ya the dfa is correct but regular expression is wrong..
0
@habib the regex provided by you is incorrect as it doesn't accept the string 'ababa'.

Pls check it.
0

@  Habibkhan sir the regular expression given by you not accepts single a or single b.

which is also the part of language

plz check ......

0
Correct regex would be

a(a + bb*a)* + b(b+aa*b)* + epsilon
0 votes
In order to check the whether there are equal occurences of two distinct expressions in a string there should be some way for us to maintain the count of each expression. And taking into account that this is an infinite relation (as there is no bound to the count ) this language is not regular. And this can also proven by pumping lemma.

A very simple example as you might already know.

L= { a^n b^n | n>=1} represents a relation which is not bound and hence it is not regular.

 On the other hand.

L= {a^n b^n| n<=3} represents a bounded finite relation and hence is regular.
by Active (4.8k points)
0
0
Thanks Arjun.  i refered the link that you gave. Please help me out on this.

 By pumping lemma's theorem if the string

ababa(please assume that length of this string is greater than the no of states in the DFA). And it E L

And by seperating the string into the sections uvw. Assume that the machine stays in the same state before and after consuming V. if V only contains the substing ab then on pumping b

ababba does not E L
0
Sorry my doubt is cleared. Even the second string belongs to L. Please ignore last comment.
0 votes
answer : language is regular

Explanation :

if you observe the language, once u get 'ab' then on the next string u could get am 'a' or 'b' making 'ba' or waiting for 'a' because on the input 'b' again. So at any point of time u can have the difference of 'ab' and 'ba' to be at most 1, not more than that. thus reducing the power of the language of a regular language.

Please comment below if further clarification is needed. i will explain u with a DFA .
by Junior (575 points)

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
50,737 questions
57,316 answers
198,359 comments
105,087 users