--- tags: compiler construction, --- # Searching for Strings: Homework ## Summary of the Lecture The automaton for Question 1, searching for `abab`, is: ![](https://i.imgur.com/N03LcaG.png) The orange transitions are obtained directly from `abab`. To figure out the other transitions, think of states as what they "remember from the past" and what they "expect from the future". I summarised this in the next table, encoding states as integers as indicated in the diagram by the magenta numbers. | State | Past | Future | |:---:|:---:|:---:| |0|`""`|`abab`| |1|`a`|`bab`| |2|`ab`|`ab`| |3|`aba`|`b`| |4|`abab`|`ab`| If you have the table above in mind, you should be able to find/explain all the transitions in the automaton. (Try it!) ## Homework (not assessed) After the lecture, you should be able to do the following: - Revise Question 1, now with the pattern `aba` instead of `abab`. (Or any other string, for that matter.) - Implement an automaton for Question 1 in your favourite programming language. The next homework needs some new ideas, but give it a try as preparation for the next lecture. - Find automata for [Questions 2 and 3](https://hackmd.io/@alexhkurz/Sk555wUlu). ## Assessed homework <font color=red>for the Report (Deadline Sunday, Feb 6) (Submission: send an email to me with a link to the .tex and .pdf of your report in your private github repository. Template files are [here](https://github.com/alexhkurz/compiler-construction-2022/tree/main/report).) Exercise 2.2.4. items b and c in [HMU](http://ce.sharif.edu/courses/94-95/1/ce414-2/resources/root/Text%20Books/Automata/John%20E.%20Hopcroft,%20Rajeev%20Motwani,%20Jeffrey%20D.%20Ullman-Introduction%20to%20Automata%20Theory,%20Languages,%20and%20Computations-Prentice%20Hall%20(2006).pdf). </font>