Aspire's Library
A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET
Study Stuff for MCA Examinations - NIMCET
Previous Year Question (PYQs)
Which of the following languages are not regular?
A. $L=\{(01)^n0^k\mid n>k,\ k\ge 0\}$
B. $L=\{c^nb^ka^{n+k}\mid n\ge 0,\ k\ge 0\}$
C. $L=\{0^n1^k\mid n\ne k\}$
Choose the correct answer from the options given below:
A. $L=\{(01)^n0^k\mid n>k,\ k\ge 0\}$
B. $L=\{c^nb^ka^{n+k}\mid n\ge 0,\ k\ge 0\}$
C. $L=\{0^n1^k\mid n\ne k\}$
Choose the correct answer from the options given below:
Solution
Language A compares the number of $(01)$ blocks with the number of ending $0$ symbols.
This counting comparison cannot be done by a finite automaton, so A is not regular.
Language B has form $c^nb^ka^{n+k}$.
Here, number of $a$ symbols depends on the sum of number of $c$ and $b$ symbols.
A finite automaton cannot store this count, so B is not regular.
Language C is $L=\{0^n1^k\mid n\ne k\}$.
If C were regular, then its complement within $0^*1^*$ would also be regular.
But that complement is $\{0^n1^n\}$, which is not regular.
So, C is also not regular.
Therefore, A, B and C are not regular.
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Ask Your Question or Put Your Review.
