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 :)

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.

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

Option-D

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 :)

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

x=phi y=aaaa now check

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

thks

## Pages