HW#2 --- last modified March 25 2020 19:54:55.

Solution set.

Due date: Mar 6

Files to be submitted:
  Hw2.zip

Purpose: To gain experience designing and build machines for regular languages

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO3 -- Describe a language in terms of a regular expression.

Description: This homework consists of the exercises below. Your work for all portions of this assignment should be submitted in the file Hw2.zip. Within this file, you should have a readme.txt listing each team mate. You should put the exercise solutions in the file Hw2.pdf.

1. Prove via a Cartesian product construction on DFAs that the regular languages are closed under intersection. I.e., if `L_1` and `L_2` are regular languages so is `L_1 cap L_2`.
2. Let `L = {w | mbox{w begins with 010}}` and `L' = {w | mbox{w end with 101}}`. Draw NFA's for both languages. Then use the constructions from class to make NFA's for `LL'`, `L cup L'`, and `L^\star`.
3. Show step-by-step how the algorithm described in the remark after our theorem on membership testing would determine if 1011010 was in `L cup L'` directly from the NFA you got in the previous problem (no conversion to DFA).
4. Use the power set construction to convert your NFA from the last exercise for `L cup L'` into a DFA then do state minimization on the result.
5. Use the construction from class or the book to step-by-step convert your DFA from the last exercise to a regular expression.
6. Using the construction from class, give a right-linear grammar for the DFA you obtained above.
7. Let `L={w|w \in {0,1,2}^{\star}, mbox(the number of 0's in w is divisible by 3)}`, let `L'` subset of `L((zero)^{\star})` where the number of copies of the word "zero" is divible by three. Give a homomorphism `h` from `L` to `L'`, make a regular expression for `L` and then use this homomorphism and the construction from class to get a regular expression for `L'`.
8. Let `A={cars, car\i\n\g, buses, burnt, jum\p\e\d, jump\i\n\g}` and `B={s, ed, \i\n\g}`. Give DFAs for each of these languages. Then using Ginsberg and Spanier's construction give an automata for `A/B`.
9. In Wikimedia syntax (as say used by Wikipedia), to put text in a level `n` heading, one writes `=^n` text_one_wants_in_a_heading `=^n`. So for example, a to put "hello" in a level 2 heading one would write:

   ==hello==
   

   Let our alphabet consist of = and the letters a through z. Let `L_{leq n} = {=^iw=^i|w in\{a,b,c,...,z\}^star, i \leq n}`. Show for each `n`, `L_{leq n}` is regular.
10. Show `cup_{n \in NN }L_{leq n}` is not regular using the pumping lemma. Here `L_{leq n}` is defined as in the previous problem.