1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: When Context Free is actually Regular

  1. Dec 1, 2008 #1
    1. The problem statement, all variables and given/known data

    What is an algorithm which decides whether a context-free language is actually a subset of a regular language? That is, given CFL and RL, how do we decide whether CFL is a subset of RL?
  2. jcsd
  3. Mar 22, 2011 #2
    I do not understand. You want to decide if context free language s a subset of any regular language? It always happens. If L is CFL over alphabet A, then A* is regular and L is subset of A*.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook