Homework 8
Last updated: Mon, 7 Nov 2022 17:53:53 -0500
Out: Tue Nov 08, 00:00 EST Due: Mon Nov 14, 23:59 EST (Note the Mon deadline again)
This assignment takes a closer look at decider Turing Machines and decidable languages.
Homework Problems
Chomsky Normal Form (9 points)
An Algorithm About DFAs? (10 points)
An Algorithm About PDAs? (10 points)
Regular and Decidable? (10 points)
README (1 point)
Total: 40 points
Submitting
Submit your solution to this assignment in Gradescope hw8. Please assign each page to the correct problem and make sure your solutions are legible.
A submission must also include a README containing the required information.
1 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 any terminal, A, B, C are any variables, except B and C are not the start variable.
In addition, a grammar in CNF may include a rule S\rightarrow \varepsilon, where S is the start variable.
Convert the following context-free grammar to Chomsky Normal Form using the algorithm described in class.
E\rightarrow T \mid E \texttt{ - } T \mid \texttt{- } T
T\rightarrow T \times F \mid F
F\rightarrow \mathit{L} \mid F^{\wedge}\mathit{L}
L\rightarrow \texttt{x} \mid \texttt{1}\mid\texttt{(}E\texttt{)}
The start variable of the CFG is E and the set of terminals is \{\texttt{-},\times,\texttt{(},\texttt{)},\texttt{x},\texttt{1},^{\wedge}\}
2 An Algorithm About DFAs?
Prove that the following language is decidable:
B_{\textsf{DFA}} = \left\{\left\langle M\right\rangle\mid M\textrm{ is a DFA that accepts all strings containing a single \texttt{B} character}\right\}
If your answer involves a decider, remember that a decider must be accompanied by a termination argument.
Also, remember that if you want, you may use any other machines we’ve already constructed in class, or in previous homeworks, without re-defining them.
3 An Algorithm About PDAs?
Prove that the following language is decidable:
\mathrm{\textit{PW}} = \left\{\left\langle P,w\right\rangle\mid P\textrm{ is a PDA where }w\in Lang(P)\right\}
4 Regular and Decidable?
Here is a statement about regular languages and decidable languages:
If a language L is a regular language, then L is decidable.
Prove this statement in three ways, using each of the three representations of regular languages that we have studied.