Register

MadeEasy Test Series 2018: Theory of Computation - Identify Class Language

• edited by
563 views
2 votes
2 votes

• edited by
User Avatar

2 Answers

1 votes
1 votes

Correct answer is L2 and L4 

EXPLANATION :

L1: 2 comparisons so not CFL

L2: 1 comparison so CFL

if you look through it properly you will see that the union (i<=j) U (j<=i) means i and j can be anything(since i can be less than or equal to j OR j can be less than or equal to i). So there is just one comparison.

L3: more than 1 comparison so not CFL |b| = |c| , |a| != |b| , |c| != |d|

L4: 1 comparison so CFL

p --> q which is equivalent to (not p or q )

where

p : |a| = |b|

q : |c| is even

if p is false , directly accept the string

if p is true, check for even no. of c which can be done by DFA

  

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2 votes
2 votes
1 answer
2
Sumaiya23 asked Jan 22, 2018
458 views
MadeEasy Test Series 2018: Theory of Computation - Identify Class Language
a) Only L1 is correct b)Only L2 is correct c)Both L1 and L2 are correct d)None of L1 and L2 is correct My question is: What is meant by prefix of string? And how is L1 regular?
a) Only L1 is correctb)Only L2 is correctc)Both L1 and L2 are correctd)None of L1 and L2 is correctMy question is: What is meant by prefix of string? And how is L1 regula...
User Avatar
2 votes
2 votes
5 answers
4
air1ankit asked Dec 9, 2017
847 views
MadeEasy Test Series: Theory Of Computation - Identify Class Language
If L1 = { a^n | n ≥ 0 } and L2 = { b^n | n ≥ 0 }, Consider then L1 . L2 wil be a) (ab)^n b) a^n b^n c) b^n a^n d)b^m a^n e) { a^m b^n | m ≥ 0, n ≥ 0 } why answer is d why not b ????
If L1 = { a^n | n ≥ 0 } and L2 = { b^n | n ≥ 0 }, Considerthen L1 . L2 wil bea) (ab)^nb) a^n b^nc) b^n a^nd)b^m a^ne) { a^m b^n | m ≥ 0, n ≥ 0 }why answer is d w...
User Avatar
Link Copied!