1. e* | a* | b* | (a|b)*
2. ((a* b*)* (b*a*)*)*
3. (a*b)* | (b*a)*
4. (a|b)* a (a|b)*

1. All strings in S* with no more than three a's.
2. All strings in S* with a number of a's divisible by three.
3. All strings in S* with exactly one occurrence of the substring aaa.

1. baa Î L(a*b*a*b*)
2. L(b*a*) Ç L(a*b*) = L(a*) È L(b*)
3. L(a*b*) Ç L(b*c*) = Æ
4. abcd Î L(a(cd)*b)*

1. Consider the following non-deterministic finite automaton:

   State	Symbol	d(State,Symbol)
   0	a	0
   0	a	1
   1	b	1

   where the start state is 0, and the accepting state is 0.

   Indicate whether or not each of the following strings is accepted by this NFA:

   1. a
   2. aa
   3. aab
   4. e
   
   
2. Consider the following non-deterministic finite automaton:

   State	Symbol	d(State,Symbol)
   0	a	1
   1	b	2
   1	b	3
   2	a	3
   3	a	1

   where the start state is 0, and the accepting states are 0 and 3.

   Indicate whether or not each of the following strings is accepted by this NFA:

   1. e
   2. ab
   3. abab
   4. aba
   5. abaa

S -> aS
S -> bS
S -> aA
S -> a
A -> aA
A -> bA
A -> a
A -> b

Construct a finite state automaton which can be used to recognise the same language.

1. {ww^r | w Î {a,b}*}
2. {ww | w Î {a,b}*}