UGCNET DEC2019 Part2
October 4, 2023OperatingSystems
October 4, 2023TheoryofComputation
Question 15

Consider the following languages:
L 1 is not contextfree but L 2 and L 3 are deterministic contextfree.


Neither L 1 nor L 2 is contextfree.


Neither L 1 nor its complement is contextfree.

Question 15 Explanation:
L1=ww is a wellknown CSL (nonCFL) and its complement is CFL.
L2={an bn cm  m,n >=0} this contains only one comparison (number of a’s = number of b’s) so this is DCFL.
L3={am bn cn  m,n >=0} this contains only one comparison (number of b’s = number of c’s) so this is DCFL.
Intersection of L2 and L3 will have (number of a’s= number of b’s = number of c’s) i.e., {an bn cn  n >=0} so this is CSL (nonCFL).
So A is a true statement and rest all are false statements.
L2={an bn cm  m,n >=0} this contains only one comparison (number of a’s = number of b’s) so this is DCFL.
L3={am bn cn  m,n >=0} this contains only one comparison (number of b’s = number of c’s) so this is DCFL.
Intersection of L2 and L3 will have (number of a’s= number of b’s = number of c’s) i.e., {an bn cn  n >=0} so this is CSL (nonCFL).
So A is a true statement and rest all are false statements.
Correct Answer: D
Question 15 Explanation:
L1=ww is a wellknown CSL (nonCFL) and its complement is CFL.
L2={an bn cm  m,n >=0} this contains only one comparison (number of a’s = number of b’s) so this is DCFL.
L3={am bn cn  m,n >=0} this contains only one comparison (number of b’s = number of c’s) so this is DCFL.
Intersection of L2 and L3 will have (number of a’s= number of b’s = number of c’s) i.e., {an bn cn  n >=0} so this is CSL (nonCFL).
So A is a true statement and rest all are false statements.
L2={an bn cm  m,n >=0} this contains only one comparison (number of a’s = number of b’s) so this is DCFL.
L3={am bn cn  m,n >=0} this contains only one comparison (number of b’s = number of c’s) so this is DCFL.
Intersection of L2 and L3 will have (number of a’s= number of b’s = number of c’s) i.e., {an bn cn  n >=0} so this is CSL (nonCFL).
So A is a true statement and rest all are false statements.
Subscribe
Login
0 Comments