diff -r a6093b0ad246 -r 2a62f0845f98 hws/hw05.tex --- a/hws/hw05.tex Fri Oct 20 00:01:39 2017 +0100 +++ b/hws/hw05.tex Fri Oct 20 11:29:48 2017 +0100 @@ -1,7 +1,7 @@ \documentclass{article} \usepackage{../style} \usepackage{../graphics} - +\usepackage{../grammar} \begin{document} @@ -88,6 +88,27 @@ Observe the maximal munch rule and the priorities of your regular expressions that make the process of lexing unambiguous.) +\item Given the following context-free grammar $G$ + +\begin{plstx}[margin=1cm] + : \meta{S\/} ::= \meta{A\/}\cdot\meta{S\/}\cdot\meta{B\/} \;\mid\; + \meta{B\/}\cdot\meta{S\/}\cdot\meta{A\/} \;\mid\; \epsilon\\ + : \meta{A\/} ::= a \mid \epsilon\\ + : \meta{B\/} ::= b\\ +\end{plstx} + +which of the following strings are in the language of $G$? + +\begin{itemize} +\item[$\bullet$] $a$ +\item[$\bullet$] $b$ +\item[$\bullet$] $ab$ +\item[$\bullet$] $ba$ +\item[$\bullet$] $bb$ +\item[$\bullet$] $baa$ +\end{itemize} + + \item {\bf(Optional)} Recall the definitions for $Der$ and $der$ from the lectures. Prove by induction on $r$ the property that