Homework 1
This homework is an alternative to the one in the theoretical sister course, designed to make you engage with the regular language portion of this course. It is due in two weeks (on Friday, ), electronically, or if necessary in my mailbox.
Rules
Feel free to work together as much as you’d like. However, if you work together with someone else , each of you must write up their own homework. Furthermore, please include the names of all people you worked together with, in the homework.
Assignment
- Read Angluin’s paper on learning reversable languages (focus just on the zero reversable case)
- Choose your favorite regular expression for a zero reversable language, and
- determine a characteristic sample for its language
- show what the learning algorithm does if you leave out one sentence (your favorite one) from the characteristic sample.