Exercise class Formele Talen en Automaten 1, spring 2003

(De informatie op deze pagina is ook in het Nederlands beschikbaar).

Home work exercises

In the course of the semester, some homework exercises will be set. Students that make these exercises and hand in their solutions in time (we are strict in this), can gain a bonus of 0.20 or 0.25 point for the exam per time. Students that hand in only part of the homework exercises, can only gain part of the maximal bonus. The bonus is only valid for the exam of Tuesday, 27 May, 2003. Solutions can be handed in to Rudy van Vliet.

Homework exercise 1

In the exercise class at 4 February 2003, we have made the first part of exercise 3.21. Students present know now how to make a finite automaton (with λ-edges) that recognizes the given language K.
Now construct a deterministic finite automaton (without λ-edges) for K and determine a regular expression for K using the method of Brzozowski and McCluskey. Also give intermediate results.
Submission deadline: 18 February, 2003.
Maximal bonus: 0.20 point.
This homework exercise has been corrected! You can get back your solutions provided with comments at Rudy van Vliet. There you can also see the bonus that you gained with the exercise.

Homework exercise 2

In the exercise class at 18 February 2003, we have made the first part of exercise 3.34(a). Finish this exercise. Hand in the complete solution of exercise 3.34(a). In principle, always use the official construction, as described in section 3.11 of the lecture notes. Only the subformula `i<k<j' does not have to be rewritten into `i<j ∧ j<k'. You may construct a finite automaton for this subformula in one step.
Submission deadline: 11 March, 2003.
Maximal bonus: 0.25 point.
This homework exercise has been corrected! You can get back your solutions provided with comments at Rudy van Vliet. There you can also see the bonus that you gained with the exercise.

Homework exercise 3

In this homework exercise, you have to use the pumping lemma for context-free languages (Theorem 4.42). The homework exercise consists of two parts: exercise 4.14 (K1) and exercise 4.15, both from the regular collection of exercises.
In exercise 4.14 (K1), you have to show that the given language K1 is not context-free. You can do so using the pumping lemma.
In exercise 4.15, you have to show that the pumping lemma cannot be reversed: there do exist languages that can be `pumped', although they are not context-free. The given language K is an example of that, and you have to prove that. Hence, show that K does have the property of the pumping lemma (K can be `pumped'), but that K is not context-free. For the latter part, you can use the closure properties of CF, as given in section 4.9 of the lecture notes (possibly combined with the pumping lemma).
Submission deadline: 15 April, 2003.
Maximal bonus: 0.25 point.
This homework exercise has been corrected! You can get back your solutions provided with comments at Rudy van Vliet. There you can also see the bonus that you gained with the exercise.

Homework exercise 4

In this homework exercise, you must demonstrate that your able to apply the construction from Theorem 5.16 `in practice'. We are given the context-free language K = {aⁱb^jc^k | i, j, k ≥ 1, i = j+2k} and the homomorphism h from Φ = {a, b, c, d} to Δ = {a, b, c} defined by h(a) = aabc, h(b) = bc, h(c) = λ (lambda), h(d) = a. Now construct a pushdown automaton for h^-1(K). The complete construction consists of six steps. You have to go through all these steps (which is not so much work as it may seem):

Step 1: Construct a context-free grammar G for K. It is possible to construct a grammar G with four productions. If you have more productions, then you may have to do more work at a later stage.
Step 2: Transform G into the Chomsky normal form or the Greibach normal form. You may choose yourself which of the two normal forms you use.
Step 3: Construct a pushdown automaton A such that K is the empty-stack language of A. Use the construction from Lemma 5.10 for this.
Step 4: Construct a pushdown automaton A' such that K is the final-state language of A'. Use the construction from Lemma 5.7 for this.
Step 5: Determine the set Buf occurring in the proof of Theorem 5.16, which corresponds to the homomorphism h.
Step 6: Construct a pushdown automaton A'' such that h^-1(K) is the final-state language of A''. Use the construction from Theorem 5.16 for this. You may leave out/remove `useless' states. In that case, you must make clear why the states you left out/removed were `useless'.

After having finished this construction: argue what h^-1(K) looks like, i.e., which strings it contains.
Submission deadline: Monday, 12 May, 2003.
Maximal bonus: 0.25 point.
This homework exercise has been corrected! You can get back your solutions provided with comments at Rudy van Vliet. There you can also see the bonus that you gained with the exercise.

Last modified: 19 May, 2003

Questions and comments can be sent to: rvvliet@liacs.nl.