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

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)