Homework 4
Last updated: Thu, 4 Nov 2021 14:27:22 -0400
Out: Mon Oct 4, 00:00 EST Due: Sun Oct 17, 23:59 EST (Note: 2 weeks!)
This assignment explores context-free languages.
Homework Problems
Deriving Strings Using CFGs (3 + 2 + 2 + 2 = 9 points)
CFL Proof of Correctness (only if) (5 points)
A CFG For Matching Braces (5 + 5 = 10 points)
A PDA for Matching Braces (5 points)
NFA->PDA (4 points)
A CFG Theorem (5 points)
README (2 point)
Total: 40 points
Submitting
Submit your solution to this assignment in Gradescope hw4. Please assign each page to the correct problem.
A submission must include a README containing the required information, in addition to the solution to the problems.
1 Deriving Strings Using CFGs
Here’s a CFG representing a tiny subset of JavaScript.
\left\langle EXPR\right\rangle | \rightarrow | \left\langle ID\right\rangle \mid \left\langle NUM\right\rangle \mid \left\langle STR\right\rangle \mid \left\langle EXPR\right\rangle \texttt{+} \left\langle EXPR\right\rangle \mid \texttt{func (} \left\langle IDS\right\rangle \texttt{)} \{\texttt{ return } \left\langle EXPR\right\rangle \} |
\mid\left\{\left\langle PROPS\right\rangle\right\}\mid \left\langle EXPR\right\rangle \texttt{.} \left\langle ID\right\rangle \mid \left\langle EXPR\right\rangle\texttt{[}\left\langle STR\right\rangle\texttt{]} \mid \left\langle EXPR\right\rangle \texttt{.} \left\langle ID\right\rangle \texttt{=} \left\langle EXPR\right\rangle | ||
\left\langle PROPS\right\rangle | \rightarrow | \left\langle PROP\right\rangle, \left\langle PROPS\right\rangle \mid \left\langle PROP\right\rangle \mid \varepsilon |
\left\langle PROP\right\rangle | \rightarrow | \left\langle ID\right\rangle:\left\langle EXPR\right\rangle |
\left\langle NUM\right\rangle | \rightarrow | 0\mid 1\mid 2\mid 3\mid 4\mid 5\mid 6\mid 7\mid 8\mid 9 |
\left\langle STR\right\rangle | \rightarrow | \texttt{"}\left\langle ID\right\rangle\texttt{"} |
\left\langle IDS\right\rangle | \rightarrow | \left\langle ID\right\rangle \left\langle IDS\right\rangle \mid \varepsilon |
\left\langle ID\right\rangle | \rightarrow | \texttt{a}\mid\texttt{b}\mid\texttt{c}\mid\cdots\mid\texttt{x}\mid\texttt{y}\mid\texttt{z} |
(Yes, real-world languages are much more complicated than textbook examples.)
To help readability, variable names are enclosed in angle brackets, e.g., \left\langle EXPR\right\rangle is a variable name. All other symbols used in the rules are terminals.
Give a formal description of this grammar. You may assume that the rules are already given (i.e., you don’t need to rewrite them into your solutions).
- Give derivations or parse trees for the following strings:
\texttt{func (x y) \{ return x + y \}}
\texttt{\{a: 1, b: "x"\}["a"]}
\texttt{\{z: 1\}.z = 2}
2 CFL Proof of Correctness (only if)
Complete the proof of correctness for the language L = \left\{\texttt{0}^n\texttt{1}^n\mid n\geq 0\right\} and the CFG that we started in class:
G = A\rightarrow \texttt{0}A\texttt{1}\mid\varepsilon
Specifically, prove the following statement:
\textrm{For any string } w\in\Sigma^*, \textrm{ if }A\Rightarrow^*w\textrm{ then } w\in L
where \Sigma is the set of terminals of G. Use induction on the length of w.
Make sure your proof covers all the possible cases and that every step in the proof has a justification.
3 A CFG For Matching Braces
The syntax of many programming languages allows nested code blocks, where each block must begin with an open brace and must end with a close brace.
The language of all strings of matching braces captures the essence of these programming languages. Call this language B\!B.
Here are some strings that are in this language:\{\{\}\}
\{\}\{\}
\{\{\}\{\}\}
\varepsilon
Here are some strings that are not in the language:\lbrace
\rbrace
\rbrace\lbrace
\lbrace\rbrace\lbrace
Come up with a CFG for the language B\!B.Prove the correctness statement:
\textrm{For all strings }w, w\in B\!B \textrm{ if and only if } S\Rightarrow^* w where S is the start variable in your grammar.
4 A PDA for Matching Braces
Come up with a PDA for the grammar you created in the previous problem A CFG For Matching Braces.
5 NFA->PDA
Come up with a conversion function \texttt{NFA}\!\rightarrow\!\texttt{PDA} that, given some NFA N = (Q_N,\Sigma,\delta_N,q_N,F_N), produces an equivalent P = (Q_P,\Sigma,\Gamma,\delta_P,q_P,F_P).
This also proves that every regular language is also a CFL! (Note: the opposite is not true)
6 A CFG Theorem
Prove that for any grammar, if \alpha\Rightarrow^*\beta and \beta\Rightarrow^*\gamma, then \alpha\Rightarrow^*\gamma.
You may want to use induction on the number of steps in one of the derivations.