Compilers: Principles and Practice

EXERCISES

1. We delete from the set of states Q of an FSM M, all the states not reachable from q₀ and get a new FSM M₁. Is it true that L(M₁) = L(M)?
2. Consider a set A = {1, 2, 3} and a relation R : A → A, R = {(1, 2), (2, 2), (1,1)}. What is the nature of R?
3. In some NDFSM with ε transitions, there is a state with e transition to itself. What is the language recognized by a new machine in which this transition is deleted?
4. State True/False:
   1. The language L(R) for any regular expression R is sometimes finite.
   2. If R does not have any * or +, then L(R) is always finite.
5. Give inductive proofs for:
   1. If REV(x) is reverse of any string x, then REV(REV(X)) = x.
   2. Let a language L be defined as: (i) a ∈ L, (ii) if some x ∈ L then (x) ∈ L. Prove that any string ...