search
Log In
3 votes
141 views

$L_1 =\{a^n b^m c^n \mid m,n \geq 0\}$ and $L_2=\{ a^n b^n\mid n\geq 0\}$. If $L=L_2-L_1$ then $L$ is

  1. finite language
  2. regular language
  3. DCFL  
  4. not DCFL
in Theory of Computation 141 views
2

L=L2-L1 = { a^n b^n|n>=1} and hence it is DCFL

0
@manu, no it is not an empty string. Whatever be the common element between L1 and L2 should be removed from L2. Here common element is epsilon.
0

an bm cn here we need to see a and b can be equal but c will also be equal so an bn  can never be exept for n=0 generated by L1

0

@Manu

see in, L1 only epsilon is common with L2, because whenever you try to take string containing 'a' in L1,  'c' will also come in that string...but there is no string containing 'c' in L2, so only epsilon in L1 is common with L2,

therfore L=L2-L1 = { a^n b^n|n>=1}

1 Answer

6 votes
 
Best answer

Option C.

strings in L1 ={epsilon, ac, abc, aabcc, ...........}

string in L2 = {epsilon , ab, aabb, aaabbb.........}

in both language only epsilon is common

L2-L1 = { ab, aabb, aaabbb........}

={a^n b^n | n>0} which is DCFL


selected by
0
if m=0, then L1 can generate ab, aabb, aaabbb, and so on.. right?
0
if m=0, then it can only generate a^n c^n
0
yes, i didn't notice!
0
L = L2 - L1  can be written as L2 INTERSECTION L1'  COMPLEMENT OF L1 IS DCFL L2 is already DCFL NOW intersection of two dcfl is not closed  it means it may or may not be dcfl but here it is dcfl am i right?

Related questions

2 votes
2 answers
2
4 votes
2 answers
3
509 views
$L1= \{a^mb^nc^k\;|\;if\,(m=n)\,then\,(n!=k)\} \\ L2= \{a^ib^jc^k\;|\;if\,(i<j)\,then\,(k<j)\}\\ L3= \{a^ib^jc^k\;|\;(i<j)\,\leftrightarrow \,(k<j)\}$ Could someone please help to conclude the class of above languages? Below mentioned is the logic used to conclude that L1 and L2 are CFL but ... ( i<j) and comp( k<j) ] or [ (i<j) and (k<j) ] = [ (i>=j) and (k>=j) ] or [ ( i<j) and ( k<j) ] = CSL
asked Nov 17, 2016 in Theory of Computation yg92 509 views
3 votes
1 answer
4
485 views
Is the language $L=\left \{ (0^{n}1^{n})^{*} |n\geq 0 \right \}$ is DCFL ?
asked Oct 21, 2016 in Theory of Computation saurabh rai 485 views
...