CS 230 Winter 2024
Tutorial 11
Coverage: DFA, NFA, and Regular Expressions
Note: Transitions which represent the situation where you move from one state to another without consuming input are represented in different ways. Module 4 refers to ϵ (epsilon) transitions. Other sources use λ (lambda) to represent these kinds of transitions. Both are acceptable.
There are other correct DFAs, NFAs and REs to these problems beyond those shown as model solutions.
1. Describe the language defined by the following DFA:
2. Describe the language defined by the following DFA:
3. Draw a DFA over the alphabet Σ = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, . that accepts any positive floating point numbers in base-10 (i.e. numbers that must include a decimal point).
4. Draw a DFA over the alphabet Σ = a, b, c that accepts strings that contain an even number of a characters and any number of b characters and c characters.
5. Which of the strings satisfies the following regular expression, where the alphabet is all lower case letters:
ma.e arr∗gh (re)+
(a) mae agh ϵ
(b) mace arrgh rere
(c) ϵ arrrgh ϵ
(d) make agh re
6. Draw a DFA or NFA that matches the following regular expressions:
(a) (a|b)∗aba(bba)+ where Σ = {a, b}
(b) a∗b.ba∗ where Σ = {a, b, c}
7. Write a regular expression and draw an NFA or a DFA that accepts simple mathematical expression that combines variables x and y with the mathematical operators +, −, ∗, and /. No brackets are allowed in the expression.
For example, these are valid expressions:
• x
• x + y
• y–x ∗ x/y
These are invalid expressions
• xy
• x +
• y + - x