The Gateway to Computer Science Excellence
+3 votes

$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 by Boss (10.6k points) | 118 views

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

@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.

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



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

by Loyal (7.8k points)
selected by
if m=0, then L1 can generate ab, aabb, aaabbb, and so on.. right?
if m=0, then it can only generate a^n c^n
yes, i didn't notice!
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?
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,567 answers
101,708 users