Homework: Regular Expressions and Finite Automata

Automata maybe drawn either as state diagrams or transition tables

Use only the three regular expression operators for this homework. plus any parentheses used to make order of operations explicit.

1. alternation, e.g., a|(bc)
2. concatenation, e.g., ab
3. Kleene closure, e.g., (ab)*

The order of operations, from highest to lowest, is Kleene closure, concatenation, and alternation.

1. Which one of the following is true about regular languages?
   • A regular language can contain an infinite number of strings
   • A regular language must contain an finite number of strings
   • A regular language can parse a context-free grammar
   • A regular language cannot be expressed with regular expressions

2. Write 3 strings that this regular expression matches

   ((b|c)a(d|t))*

3. Write a regular expression for the following language description: zero or more letters "a" followed by either letter "c" or letter "d".

4. Convert this regular expression to a nondeterministic finite automaton (NFA). Recall that concatenation is a higher precendence than alternation.

   (aba|bab)*c

5. Convert the NFA above into a deterministic finite automaton (DFA)