When Context Free is actually Regular

  • Thread starter Thread starter Dragonfall
  • Start date Start date
  • Tags Tags
    Regular
Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
1 reply · 2K views
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*.