Homework 7
Last updated: Wed, 24 Mar 2021 19:20:17 -0400
Out: Mon March 29, 00:00 EST Due: Sun April 4, 23:59 EST
This homework covers material from chapter 4 of the textbook.
Homework Problems
Regular Expressions and DFAs (6 points)
Equivalence of Regular Expressions and DFAs (6 points)
Forward but not Backwards (6 points)
Chomsky Normal Form (6 points)
CFLs that include the Empty String (6 points)
README (2 points)
The Complement Operation for Regular Languages (Bonus) (optional) (3 bonus points)
Total: 32 (+ 3 bonus) points
Submitting
Submit this assignment at Gradescope hw7.
should only include pdf or plain text files,
and each file must be assigned to the correct problem in Gradescope.
1 Regular Expressions and DFAs
Give a constructive proof of the following theorem:
\textrm{every regular expression } R \textrm{ has an equivalent DFA } D
where equivalent means that they represent the same language, i.e., L(R) = L(D).
Your proof may use any theorems already proven in class or in the textbook.
2 Equivalence of Regular Expressions and DFAs
Prove that it’s decidable to compute whether a DFA and regular expression are equivalent.
In other words, implement a decider for the following language:
\{\left\langle D,R \right\rangle\mid D \textrm{ is a DFA}, R \textrm{ is a regular expression, and } L(D)=L(R)\}
Your decider may use algorithms from any theorems already proven in class or the textbook, including the one you just proved for Regular Expressions and DFAs.
Also, don’t forget to explain why your decider always halts.
3 Forward but not Backwards
Show that the following language is decidable:
\{\left\langle D\right\rangle\mid D \textrm{ is a DFA that accepts a string } w \textrm{ only if it does not accept } \textrm{FLIP}(w)\}
where \textrm{FLIP}(w) is w reversed.
You may use any theorems previously proved in class or the textbook. In particular, your answer from Homework 4’s The FLIP Operation problem may be useful here.
If creating a decider, don’t forget to explain why it always halts.
4 Chomsky Normal Form
Recall that a CFG is in Chomsky Normal Form (CNF) if all rules have the form:
A \rightarrow BC |
A \rightarrow \texttt{a} |
where \texttt{a} is a terminal, A, B, C are variables, and B and C are not the start variable.
In addition, a grammar in CNF may include rule S\rightarrow \varepsilon, where S is the start variable.
Convert the following CFG to Chomsky Normal Form:
S \rightarrow \varepsilon |
S \rightarrow A |
S \rightarrow ASA |
A \rightarrow \varepsilon |
A \rightarrow \texttt{11} |
This grammar has only one terminal, \texttt{1}.
5 CFLs that include the Empty String
Show that the following language is decidable:
HASEMPTY_{CFG} = \{\left\langle G\right\rangle\mid G \textrm{ is a CFG whose language includes } \varepsilon\}
If creating a decider, don’t forget to explain why it always halts.
6 The Complement Operation for Regular Languages (Bonus)
Recall (Ch 0) that the complement of a set is the set of all elements that are not in the set.
Show that regular languages are closed under the complement operation.