gotchaMinor
Difference between regular language and context free language
Viewed 0 times
freeregularlanguagedifferencebetweencontextand
Problem
What is nature of difference of regular language and context free language?
My guess is
Am I correct with this?
My guess is
RL - CFL = RL
CFL - RL = CFLAm I correct with this?
Solution
No, those are not quite correct.
For any alphabet $\Sigma$, the language $\Sigma^*$ is regular. The set difference between that and any CFG with the same alphabet is the complement of the CFG, and CFGs are not closed with respect to complement. So your first claim is incorrect.
However, CFGs are closed with repect to intersection with a regular language and regular languages are closed with respect to complement. Thus, your second claim is correct.
For any alphabet $\Sigma$, the language $\Sigma^*$ is regular. The set difference between that and any CFG with the same alphabet is the complement of the CFG, and CFGs are not closed with respect to complement. So your first claim is incorrect.
However, CFGs are closed with repect to intersection with a regular language and regular languages are closed with respect to complement. Thus, your second claim is correct.
Context
StackExchange Computer Science Q#93999, answer score: 3
Revisions (0)
No revisions yet.