CS3012: Formal Languages and Compilers
CS3518Exercises
CS3518 Formal Languages and Computability
Exercises about Finite State Automata
Students familiar with FSAs might skip some of the earlier exercises (which are identical to exercises for CS2013), focussing on the later questions about automata with output.
Questions about automata that accept a language
1. Describe in words the languages accepted by each of the following FSAs:
Answer (i):
Answer (ii):
Answer (iii):
2.Give a formal definition for FSAs which define the following languages
(i.e. specify Q, I, F, T, E using formulas or a diagram):
(i)strings containing a or ab {a, b}
Answer:
(ii)strings containing aba or bab {a, b}
Answer:
(iii)strings containing exactly one a (and any number of bs) or exactly one b (and any number of as) {a, b}
Answer:
(iv)strings containing a, ab or abc {a, b, c}
Answer:
(v)strings containing a, ba or cba {a, b, c}
Answer:
3.Give a formal definition for a FSA accepting the infinite set of strings representing numbers divisible by 2. (i.e. 0,2,4,6,8,10,12,….)
Answer:
4.Give a formal definition for a FSA accepting the infinite set of strings representing numbers divisible by 3. (this one is tricky, try (on paper) doing a division of 3 into some large number x, and see if the process you are using to deal with each new digit of x could be automated by a machine.)
Answer:
5.Give a formal definition for a FSA accepting the set of strings over {a, b} which contain an even number of a's and an even number of b's. (this one is tricky, try doing it manually for some random string of a’s and b’s. What do you need to remember as you’re going through the string? How many states will the FSA need, to remember this?)
Answer:
Questions about automata with output
6.Consider the Moore Machine in the lecture slides, which prints out a 1 every time the substring
aab is read. Construct a Mealy Machine that is equivalent to this Moore Machine.
7. Consider the Mealy Machine in the lecture slides, which adds 1 to a binary number. Construct a
Moore machine that is equivalent to this Mealy Machine. Like in the lecture slides, assume that
numbers are written inreverse order, for example write 11101 instead of 10111 to denote the
number some of us know better as 23.
8. (Only for those who are familiar with Nondeterministic FSAs.) Does it make sense to define a
nondeterministic automaton with output? If so, show how a nondeterministic Moore Machine,
and a nondeterministic Mealy Machine, could be defined.
9. Look carefully at the way in which equivalence between Moore Machines and Mealy Machines
is defined in the slides. What would be wrong with the following alternative way of defining
equivalence:
M1 and M2 are equivalent if T1=T2 and for all strings w in T1*
M1O(w) = M2O(w)
10. Find an example on the web of a real-life problem that can be solved by a Moore or Mealy
Machine. Which of the two do you consider most suitable for the problem, and why?
11. (Optional) Hidden Markov models are among the most widely used (sophisticated) Finite State
Automata. Find an example on the web and try to figure out how it works.