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.
- Show step-by-step how the string 00001001001 would be compressed by the SEQUITUR algorithm.
- 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).
- Draw a PDA for the language `{ww^R | w in {0,1}^{star}}` (2pts).
- 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.
- (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).
Point Breakdown
Problems 1-5, (2pts each) | 10pts |
Total | 10pts |
|