The Gateway to Computer Science Excellence
+1 vote

Hi, I am having a doubt understanding the result of CFL – Regular:

Here’s my approach:

  1. CFL – Regular = CFL INTERSECTION Regular’ = CFL INTERSECTION Regular = CFL
  2. Suppose some CFL L1= {a^n b^n | n>=1} and some Regular R1= (a+b)* : 

Now if I do CFL – Reg = {ab,aabb,aaabbb, ….} – { epsilon, a, b, ab, aabb, aaabbb, …..} 

It gives { phi } which is Regular (hence also CFL)

So is it better to say CFL – Regular = Regular or CFL – Regular = CFL ? If both are separate options, which one should I go for? Thanks


in Theory of Computation by (39 points) | 50 views

1 Answer

0 votes
CFL. Because a regular language is also a context free language, as you can make a context free grammar from the D.F.A of the corresponding regular language.
by Active (2.3k points)

Related questions

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,654 questions
56,169 answers
94,303 users