equal
deleted
inserted
replaced
1 \documentclass{article} |
1 \documentclass{article} |
2 \usepackage{../style} |
2 \usepackage{../style} |
3 \usepackage{../graphics} |
3 \usepackage{../graphics} |
4 |
4 \usepackage{../grammar} |
5 |
5 |
6 \begin{document} |
6 \begin{document} |
7 |
7 |
8 % explain what is a context-free grammar and the language it generates |
8 % explain what is a context-free grammar and the language it generates |
9 % |
9 % |
86 |
86 |
87 In case they can, give the corresponding token sequences. (Hint: |
87 In case they can, give the corresponding token sequences. (Hint: |
88 Observe the maximal munch rule and the priorities of your regular |
88 Observe the maximal munch rule and the priorities of your regular |
89 expressions that make the process of lexing unambiguous.) |
89 expressions that make the process of lexing unambiguous.) |
90 |
90 |
|
91 \item Given the following context-free grammar $G$ |
|
92 |
|
93 \begin{plstx}[margin=1cm] |
|
94 : \meta{S\/} ::= \meta{A\/}\cdot\meta{S\/}\cdot\meta{B\/} \;\mid\; |
|
95 \meta{B\/}\cdot\meta{S\/}\cdot\meta{A\/} \;\mid\; \epsilon\\ |
|
96 : \meta{A\/} ::= a \mid \epsilon\\ |
|
97 : \meta{B\/} ::= b\\ |
|
98 \end{plstx} |
|
99 |
|
100 which of the following strings are in the language of $G$? |
|
101 |
|
102 \begin{itemize} |
|
103 \item[$\bullet$] $a$ |
|
104 \item[$\bullet$] $b$ |
|
105 \item[$\bullet$] $ab$ |
|
106 \item[$\bullet$] $ba$ |
|
107 \item[$\bullet$] $bb$ |
|
108 \item[$\bullet$] $baa$ |
|
109 \end{itemize} |
|
110 |
|
111 |
91 \item {\bf(Optional)} Recall the definitions for $Der$ and $der$ |
112 \item {\bf(Optional)} Recall the definitions for $Der$ and $der$ |
92 from the lectures. Prove by induction on $r$ the |
113 from the lectures. Prove by induction on $r$ the |
93 property that |
114 property that |
94 |
115 |
95 \[ |
116 \[ |