Convert the following regular expressions into nondeterministic finite automata using the method shown in the videos.
computer science
Description
Question
1
Write regular
expressions which describe the following languages. Remember your answers must
only use symbols from definition 3.5, i.e., letters from the alphabet (which
is {0,1}{0,1} in each case), (( ,)), εε, ∅∅, ∪∪, and ∗∗.
Try to write the regular
expressions from scratch rather than converting equivalent NFAs. If you decide
to do the latter, make sure your result is as simple as possible.
- {w∈{0,1}∗|w ends with 101}{w∈{0,1}∗|w ends with 101}
- {w∈{0,1}∗|w starts with 10 and ends with 1}{w∈{0,1}∗|w starts with 10 and ends with 1}
- {w∈{0,1}∗|w contains the substring 01}{w∈{0,1}∗|w contains the substring 01}
- {w∈{0,1}∗|w does not contain the substring 01}{w∈{0,1}∗|w does not contain the substring 01}
- {w∈{0,1}∗|w contains exactly one occurrence of 01}{w∈{0,1}∗|w contains exactly one occurrence of 01}
- {w∈{0,1}∗|w has a 1 in the third
position}{w∈{0,1}∗|w has
a 1 in the third position}
- {w∈{0,1}∗|w has even length}{w∈{0,1}∗|w has even length}
- {w∈{0,1}∗|w has an odd number of 0}{w∈{0,1}∗|w has an odd number of 0}
- {w∈{0,1}∗|w has an odd number of 0’s or an even number
of 1’s}{w∈{0,1}∗|w has an odd number
of 0’s or an even number of 1’s}
Question
2
Convert the following
regular expressions into nondeterministic finite automata using the method
shown in the videos. Represent the automata in the form of diagrams. You should
simplify your models as you build them – for example you may remove redundant
states and combine states that are linked with epsilon transitions, but
make sure the language is unchanged.
- (aba∪bb∪ba)∗(aba∪bb∪ba)∗
- ab(a∪b)∗a(a∪b)∗ab(a∪b)∗a(a∪b)∗
- a(bb)∗∪aba(bb)∗∪ab
- b∗a∗(ba∪b∗)b∗a∗(ba∪b∗)
Question
3
Convert these
nondeterministic finite automata (repeated from Problem Sheet 1) into regular
expressions using the method shown in the lessons. Show your working.
Note: the order in
which you remove states in the conversion process will greatly affect the
complexity of the resulting regular expression. Try to choose this order in a
way that creates the simplest result. You might want to try multiple options
before deciding which one to use for your submission.
