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