Automata

Trent University Computing and Information Systems 3050H

Winter 2015 Assignment 1: Due February 5, 2015

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}

5) Convert the following TG into a Regular Expression (show the individual steps).

6) Consider the following FAs. a) Describe in English, the language accepted by these FAs.

1 2b) Build an FA that accepts FA + FA . Use Kleene’s Theorem (show your work).