# Virtual Gate Test Series: Theory Of Computation - Regular Languages

2.4k 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$

edited
1
It is regular

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

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)*.

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
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.
0

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.

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 .

## Related questions

1
445 views
For $A,B\subseteq \Sigma ^{*},$ define $A/B=\{x\in\Sigma^{*}\mid \exists y\in B,xy\in A\}$ If $L$ is a $\text{CFL}$ and $R$ is $\text{Regular},$ then $L/R$ is$?$ Regular CFL but not Regular Recursive but not CFL None of the above
Let A be a regular set . Consider the two sets below: L1 = {$x \mid \exists{n}\geq 0 , \exists{y} \in A : y =x^{n}$} L2 = {$x \mid \exists{n}\geq 0 , \exists{y} \in A : x =y^{n}$} Which of the following is True ? L1 and L2 are Regular L1 is Regular but Not L2 L2 is Regular but Not L1 Both are not Regular
Answe is B, but why is L2 not regular? How to solve it? For L2, $y=x^{1/n}$ I am not understanding why is this not right?