Question

5. Let A={a,b,c} and let K, L C A be languages described as follows: K = {a"y":n in e Zo} and L = {a?,62,c2-free words over A}. Thus L is the language of all words over A that have no consecutive letters that are the same. (a) Give a recursive description of K. (b) Construct a finite state automaton (FSA) that accepts L.

Answer 1

Q. 5 Solution :

(a) $\huge \kappa = \{a^nb^n : n \ \varepsilon \ \mathbb{Z}_{\geq 0} \}$ can be recursively defined using the following three rules :

Rule 1. The empty string $\huge \epsilon$ belongs in $\huge \kappa$ .

Rule 2. If $\huge w$ belongs in $\huge \kappa$ , then $\huge awb$ also belongs in $\huge \kappa$ .

Rule 3. No strings can be in $\huge \kappa$ if it cannot be produced by using above two rules.

(b) We construct a Deterministic Finite Automata (DFA) for the language $\huge \mathcal{L} = \{a^2,b^2,c^2 \text{ -free words over A}\}$

In the automata below : q0 is the initial state. q0, q1, q2 and q3 are the final states. q4 is the trap/dead state which we reach when we see aa or bb or cc in the string.

q1 a,b,c b,c 6 b 90 92 94 a,c a,b q3