Reference no: EM13772239

1) Give a recursive definition for the following language over the alphabet {a, b} The language AA of all words containing the substring aa

2) Consider the following recursive definition of 4-PERMUTATION:

Rule 1: 1234 is a 4-PERMUTATION.

Rule 2: If xyzw is a 4-PERMUTATION, then so are wzyx and yzwx.

Rule 3: no other words in 4-PERMUTATION.

Write all the words in the language 4-PERMUTATION.

3) Construct a regular expression defining each of the following languages over the alphabet {a, b}.

(a) L = {aab, bba, bbb};

(b) The language of all strings containing exactly two a's.

(c) The language of all strings containing at least two a's.

(d) The language of all strings that do not end with ab.

(e) The language of all strings that do not containing the substring aa.

(f) The language of all strings in which every a is followed immediately by bb.

4) For the alphabet S={a, b}, construct an FA that accepts the following languages (be sure it is an Finite Automata (FA) that you provide and not a Transition Graph (TG)).

(a) L = {all strings with exactly one a}.

(b) L = {all strings with at least one a}.

(c) L = {all strings with no more than three a's}.

(d) L= {all strings with at least one a and exactly two b's}

(e) L= {all strings with b as the second letter}

(f) L={w, |w| mod 3 =0}