HW 06 6.11 Regular languages

1. Simulate Thompson and Glushkov constructions of creating NFA automaton from the regular expression (aa|b)*b(ab|bb)*

2. Give an automaton and a regular expression for both of the regular languages described below. In both cases, the alphabet is {a,b,c}.

a) the set of all strings containing exactly three b's.

b) the set of all strings that have a as one of the last three symbols in the string (some example strings in the set: aaa, baa, cba, cabaab, bacc, bcccbacc).).

3. Provide a regular expression recognising the set of all strings where every character of {a,b,c} is present even number of times.

4. Draw the respective automaton for a language from 3. (Can you draw directly or use Thompson construction, or perhaps draw such an automaton direct?)

5. Write a simplified pseudocode for matching NDA constructed by Glushkov method (no epsilon-transitions)