2 votes

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$

Note$:-$ $aba ∈ L $since $'aba'$ contains $1$ occurrence of $'ab'$ and $1$ occurrence of $'ba'$ but $ abab ∉ L$

7 votes

Best answer

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

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

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

0

@habib the regex provided by you is incorrect as it doesn't accept the string 'ababa'.

Pls check it.

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

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

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

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

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 .