1

In this question, I want to know what the symbol ≤ means. If it denotes reducible, what is the relationship between reduction and regular language? Or, I need an example to illustrate this relationship between two regular language. THX!

Old Panda
  • 143

1 Answers1

0

This symbol means reduction. If we have A≤B, then $w\in A$ iff $f(w)\in B$, where $f$ is the mapping relation from A to B. In this question, regular language is just a kind of language that can be feed into some Turing machine. We can just regard it as a general language in the other "decidable" language.

Old Panda
  • 143