Q61.Marks: +2.0UGC NET Paper 2: Computer Science 26th Nov 2021
Which of the following languages are not regular?
A. L = {(01)n 0k | n > k, k >= 0}
B. L = {cn bk an + k | n >= 0, k >= 0}
C. L = {0n 1k | n ≠ k}
Choose the correct answer from the options given below :
1.A and B only
2.A and C only
3.B and C only
4.A, B and C✓ Correct
Solution
L = {(01)n 0k | n > k, k >= 0} - NOT Regular => The above language is not regular because it has to maintain two variables "n" and "k". This is not possible in a regular language.
L = {cn bk an + k | n >= 0, k >= 0} - NOT Regular
=> Here also, we need to keep track of two variables, "n" and "k" because number of times "a" will occur, depends on n+k.
L = {0n 1k | n ≠ k} - NOT Regular
=> The same problem goes here as well, the number of times 1s will appear, depends on the number of times 0s will appear because the their number of occurrences should not match.