⟸ Go Back ⟸

Exercise 11 (Homework 3).

(regular expressions, decidable properties)

On some decidable properties of regular expressions

Let L_r be the (regular) language represented by the regular expression r. Given as input regular expressions r and s, describe an algorithm to decide whether

1. L_{r}=L_{s}.
2. L_{r}\subseteq L_{s}.
3. L_{r}=\emptyset.
4. L_{r} is infinite.
5. L_{r}\cap L_{s}=\emptyset.
6. L_{r}\cap L_{s} is infinite.

What is the asymptotic cost of the algorithm proposed as a function of the number of symbols in r and s?