decision properties of RLs

• Infinite: unfeasible to perform exhaustive analysis - Finite representation: DFA, NFA,-NFA, RE -> RLTo answer a question about the language:

  • RL Find an algorithm which answers yes or no
  • In many cases, there are algorithms for RLs, but not for non-regular languages, even if there are finite representations for some of them.
• DECISION PROPERTIES FOR RLs

  Infinite: unfeasible to perform exhaustive analysis - Finite representation: DFA, NFA,-NFA, RE -> RL

  To answer a question about the language:

  • Find an algorithm which answers yes or no
  • In many cases, there are algorithms for RLs, but not for non-regular languages, even if there are finite representations for some of them.

  
• IS THE LANGUAGE EMPTY?

  Answer: L = ∅ is empty.

  
• DOES THE STRING w BELONG TO THE LANGUAGE?

  
• DO TWO LANGUAGE REPRESENTATIONS DESCRIBE THE SAME LANGUAGE?

  • Two RL descriptions are equivalent if they de ne the same language