made easy test series

Question

Can someone Explain these statements?

Answer 1

S1: pumping lemma is a negativity test which is used to prove that a language isn't regular. If a language doesn't satisfy the pumping lemma, then it is definitely not regular.. But if a language satisfies the pumping lemma, it may be regular or may not be regular. So S1 is false.

S2: given a grammar,  if all the production rules of the grammar of the form A->aB or A->b or A->Ba where {a, b} are terminals and {A, B} are non terminals, then the grammar is a regular grammar, otherwise the grammar isn't regular.  So as we have an algorithm by which we are able to decide whether a grammar is regular or not,  so this is decidable. So S2 is true.

S3: suppose L=$\phi$ which is a regular language and M ={aⁿbⁿ|n>=0} which is a context free language, then L.M is $\phi$ which is regular. So S3 is false.

Hence answer is (b) only S2 is correct

Comments

@Somoshree Datta 5 

S1 and S2 are easy, i get little bit comfused in S3.

S3 is still not clear...

a*b* also contains strings of type ${a^n}$${b^m}$ where n<m but in L.M (in your explanation) n>=m.

e.g. how you generate ab² ?

---

As L=a^* and M= {aⁿbⁿ|n>=0}, so L.M=a^*b^* which denotes any number of a's(i.e. 0 a's or more a's) followed by any number of b's(i.e. 0 b's or more b's). hence (a)¹(b)² is also generated by L.M. Once L gets concatenated to M, it there is no condition on the number of a's or the number of b's that can appear. The only restriction is that all a's should appear before b's and once a b has occured in the string, there can be no more a's.

---

You can't generate any string like ab²..

Explanation- number of b's in any string should always generated from language M and if we want to make b² then(n=2) ${a^n}$${b^n}$ will be equal to a²b².  If you take a* for concatenation before a^n b^n then no. of a's always >=no. of b's..

So L.M not equal to a*b*.

Give any other example for S3..

---

Sorry my analysis for S3 is incorrect. L.M cannot be regular if L is non-empty. L.M can only be regular if L is empty..so if L=$\phi$ and M={aⁿbⁿ|n>=0}, then L.M= $\phi$ and hence it becomes regular..thanks for pointing it out :)

---

Is it ok now?

---

Yes it is ok..

Even you think that S3 is false somehow but i will definitely going to get -1 in Gate if it is not clear..   Haha..:-)

Answer 2

 3.(a+b)*aⁿbⁿ is regular for n>=0

2.True checking if the grammar is not regular is decidable problem because it's complement (i.e. checking if a grammar is regular) is decidable.

If a language is regular and it's complement is also regular then it is decidable.

1. Pumpping lemma is negativity test. We use it to disprove that a languages is not regular. But reverse is not true.

Answer is b)