---
# System prepended metadata

title: 'Searching for Strings: Homework'
tags: [compiler construction]

---

---
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>