HW#4 --- last modified April 06 2020 23:25:14.

Solution set.

Due date: Apr 17

Files to be submitted:
  Hw4.zip

Purpose: To get more practice with the CFG algorithms, PDAs, compression algorithms learned in class as well as write down our first TMs.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO1 (Learning Outcome 1) -- Write a grammar for a language described otherwise.

LO7 -- Be able to use a pumping lemma to show that some languages are not regular and/or not context-free Use closure properties to simplify proofs of non-regularity of languages.

LO8 -- Be able to construct a pushdown automaton accepting a given language.

LO9 -- Construct a Turing machine accepting some simple languages.

Description:

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

1. Show step-by-step how the string 00001001001 would be compressed by the SEQUITUR algorithm.
2. Draw a PDA for the language `L` over `{0,1}` consisting of strings with twice as many `0`'s as `1`'s (0.5pt). So 001010001 would be in this language. Next draw a DFA recognizing `0^star1^star` (0.5pt). Use the algorithm from class to draw a PDA for the intersection of these two languages (1pt).
3. Draw a PDA for the language `{ww^R | w in {0,1}^{star}}` (2pts).
4. Show step-by-step how the algorithm from class for checking if a language of CFG is infinite would operate on the grammar you got for problem (1) in this group.
5. (a) Prove the language `{w-w | w in {0,1}^{star}}` is not CFL. Here - is a symbol in the TM's alphabet (1pt). (b) Give the formal definition as a 6-tuple of a TM recognizing the language `{w-w | w in {0,1}^{star} }` (0.5pt). Here - is a symbol in the TM's alphabet. (c) Show formally that your machine accepts the string `001-001` (0.5pt).