Regularity of languages

rachapalli vinay kumar @vinayrachapalli
11 Sep 2016 09:08 pm

in both the cases we have to comapre no.of a's with no.of b's, so both are non regular.


Koushik Sinha @koushiksinha
12 Sep 2016 10:09 pm

1st one is regular and  regular expression (a+b)* . how?? let take any example- ababba  here x=aba y=bba  now check no of a in x =no of b in y.  it is possible becuse  length of x or  y is not bound. so no comparision required

but in the 2nd case , it is bound  because of $ symbol. upto $ symbol , the length of x is restricted  and remaining is y. so comparison required that is done by one stack. so it is non regular.  option B  is correct here :)

rachapalli vinay kumar @vinayrachapalli
14 Sep 2016 09:11 pm

take a string "aaaa" according to case A show me the given string in it.

Koushik Sinha @koushiksinha
14 Sep 2016 09:44 pm

x=phi y=aaaa now check 

Antonio Anastasio Bruto da @antonio
15 Sep 2016 11:07 am

@hradeshpatel: As @koushiksinha has responded, perhaps I can further explain.

In language A, any string w in the language is of the form xy, however the choice of "where to split w to get parts x and y" is what is called a non-deterministic choice. Hence, given any word w, so long as there is some way of breaking w into x and y such that it fits into the criteria of belongingness to A, it can be thought of a being in A. What makes A regular? Now that's an interesting notion. Think about what the language A will actually be. The language A will contain all strings in {a,b}*. Why so? Because for any string in the set (a+b)*, the string can always be broken into an x and y such the number of a's in x is the same as the number of b's in y.

In the second language, B, because there is a deterministic choice of what the string x contains and what the string y contains, actual counting is required to compare the number of a's in x with the number of b's in y, which for an arbitrarily large number of a's and b's, a finite automaton cannot be constructed. Pumping Lemma may be used to prove this language non-regular.

Hradesh @hradeshpatel
15 Sep 2016 02:55 pm