diff -r 19de761b69e9 -r d236e75e1d55 handouts/ho05.tex --- a/handouts/ho05.tex Tue Oct 16 14:40:30 2018 +0100 +++ b/handouts/ho05.tex Mon Oct 22 23:37:11 2018 +0100 @@ -17,8 +17,8 @@ example for which there exists no regular expression is the language of well-parenthesised expressions. In languages like Lisp, which use parentheses rather extensively, it might be of -interest whether the following two expressions are -well-parenthesised (the left one is, the right one is not): +interest to know whether the following two expressions are +well-parenthesised or not (the left one is, the right one is not): \begin{center} $(((()()))())$ \hspace{10mm} $(((()()))()))$ @@ -29,7 +29,7 @@ problems, we need more powerful techniques than regular expressions. We will in particular look at \emph{context-free languages}. They include the regular languages as the picture -below shows: +below about language classes shows: \begin{center} @@ -46,10 +46,30 @@ \end{tikzpicture} \end{center} -\noindent Context-free languages play an important role in -`day-to-day' text processing and in programming languages. -Context-free languages are usually specified by grammars. For -example a grammar for well-parenthesised expressions is +\noindent Each ``bubble'' stands for sets of languages (remember +languages are sets of strings). As indicated the set of regular +languages are fully included inside the context-free languages, +meaning every regular language is also context-free, but not vice +versa. Below I will let you think for example what the context-free +grammar is for the language corresponding to the regular expression +$(aaa)^*a$. + +Because of their convenience, context-free languages play an important +role in `day-to-day' text processing and in programming +languages. Context-free in this setting means that ``words'' have one +meaning only ansd this meaning is independend from in which context +the ``words'' appear. For example ambiguity issues like + +\begin{center} +\tt Time flies like an arrow; fruit flies like a banana. +\end{center} + +\noindent +from natural languages were the meaning of \emph{flies} depend on the +surounding \emph{context} are avoided as much as possible. + +Context-free languages are usually specified by grammars. For example +a grammar for well-parenthesised expressions can be given as follows: \begin{plstx}[margin=3cm] : \meta{P} ::= ( \cdot \meta{P} \cdot ) \cdot \meta{P} @@ -66,7 +86,8 @@ In general grammars consist of finitely many rules built up from \emph{terminal symbols} (usually lower-case letters) and -\emph{non-terminal symbols} (upper-case letters inside \meta{\mbox{}}). Rules have +\emph{non-terminal symbols} (upper-case letters written in +bold like \meta{A}, \meta{N} and so on). Rules have the shape \begin{plstx}[margin=3cm]