CS46 — Homework 4


Due Thursday 20 Feb at the start of class
Starting files are available from my public cs46 folder 
cd ~/cs46/
cp -r examples/homework/wk4 homework/
git status
git add homework/wk4
git commit -m "week4 start"
git push
You may work with a partner and submit a common solution on this homework.
In lab practice
  1. A homomorphism is a function $f: \Sigma \mapsto \Gamma^*$ from one alphabet to strings over another alphabet. We can extend $f$ to operate on strings by definine $f(w) = f(w_1)f(w_2)\cdots f(w_n)$, where $w=w_1w_2\cdots w_n$ and each $w_i \in \Sigma$. We can also extend $f$ to operate on a language by defining $f(A) = \{ f(w) | w \in A \}$ for a language $A$.
    1. Describe a construction that shows the class of regular languages is closed under homomorphism. Given a DFA $M$ for $A$, and a homomorphism $f$, construct $M'$ that recognizes $f(A)$.
    2. If $M$ is a DFA is $M'$ also a DFA?
    3. Show that non-regular languages are not closed under homomorphism.
  2. Many programming languages use braces $\{ \}$ , and parentheses $()$ to group functions, blocks, classes, etc. These braces and parentheses must be balanced in the sense that you cannot have a closing brace without a previous matching opening brace, and all open braces must eventually have a matching closing brace. Design a context free grammar that generates balanced statements containing braces and parentheses. The following examples are legal: ()(); (({}){}{{}}); {}(), but (( and (} are not.
  3. Are the following statements true or false?
    1. Every subset of a regular language is regular
    2. Every regular language has a regular proper subset
    3. If $L$ is regular, then so is $\{ xy: x \in L, y \not \in L \}$
    4. $\{w : w =w^R \}$ is regular
    5. If $L$ is a regular language then so is $\{w: w \in L \text{ and } w^R \in L\}$
    6. $\{ xyx^R: x,y \in \Sigma^* \}$ is regular

Remember to run git add, git commit, and git push to submit your assignments. If you are working with a partner, both you and your partner need to hand in the lab, but I will grade the most recent push. Include both names at the top of your homework.