When Context Free is actually Regular

  • Thread starter Thread starter Dragonfall
  • Start date Start date
  • Tags Tags
    Regular
Dragonfall
Messages
1,023
Reaction score
5

Homework Statement



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?
 
Physics news on Phys.org
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*.
 
Thread 'Use greedy vertex coloring algorithm to prove the upper bound of χ'
Hi! I am struggling with the exercise I mentioned under "Homework statement". The exercise is about a specific "greedy vertex coloring algorithm". One definition (which matches what my book uses) can be found here: https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf Here is also a screenshot of the relevant parts of the linked PDF, i.e. the def. of the algorithm: Sadly I don't have much to show as far as a solution attempt goes, as I am stuck on how to proceed. I thought...
Back
Top