\documentclass{article}

\usepackage{hevea}

\oddsidemargin 0cm
\textwidth 17cm

\begin{document}


\title{CS 3100 -- Models of Computation -- Fall 2010}
\date{August 26, 2010}

\maketitle

\begin{center}
{\bf Notes 3, Handed out: August 31, 2010 during Lecture 3}
\end{center}


\begin{LARGE}

\begin{itemize}
\item Work out solutios for Assignment 1
\end{itemize}

\noindent  Concept / mathematical notation practice: Write these mathematically:
\begin{itemize}
  \item Empty string
  \item Empty set -- write this in two different ways
  \item Write out the powerset of $\{a,b\}$
  \item How many elements are there in the powerset of $\{a,b,c,d\}$?
    \begin{itemize}
    \item Each item is present or absent
    \item Let $0000$ represent ``no elements are there'' i.e. $\emptyset$
    \item Let $0001$ represent $\{d\}$
    \item Let $1001$ represent $\{a,d\}$
    \item You get the idea now. Each subset of $\{a,b,c,d\}$ is
      represented by each four-bit bit vector.
    \item How many such bit vectors are there? $0000$, $0001$, $0010$,
      etc. all the way to $1111$?
    \end{itemize}
  \item Set containining empty string
  \item Set containining empty set
  \item Set containining an empty string and an empty set (now, why
    would you do that?! 

    This is strictly allowed, but a set usually has only
    items of the same type -- either all sets or all strings.)

  \item String containing an empty set (Groan! Can you do this? No! Strings
    are not sets.)

  \item Union of set $\{a\}$ and itself

  \item The result of inserting $a$ and $b$ into $\{a\}$

    
\end{itemize}

\clearpage
\noindent Notions centered around languages

\begin{itemize}
\item A language is a set of strings
\item Empty language  : $\emptyset$
\item The language containing the empty string : $\{\varepsilon\}$
\item One is often interested in the beginning and ending patterns 
  within strings. To specify this, one can split the string into
  two pieces that can be {\em concatenated} to form the whole.

\item Concatenation of $ab$ and $cde$ is $abcde$

\item Concatenation of $\varepsilon$ and $abd$ is $abd$

\item Now I'm going to attempt to motivate the notion of
  {\em concatenation of languages}

\item When one talks about ``all possible former halves of strings'' 
  and ``all possible latter halves of strings,'' one is talking about
  the {\em language} of the first halves and the language of 
  the last halves

  \begin{itemize}
  \item Example : telephone number = area-code followed by main-number
  \item {\tt area-code = { ( d d d ) } }
  \item {\tt main-number = { ddd-dddd }}
  \end{itemize}

\item One can then talk about the language of area codes
  and language of telephone numbers, i.e., 
  $L_{ac}$  and    $L_{telno}$, and concat. these languages
\end{itemize}

\clearpage
\noindent Language concatenation
\begin{itemize}
\item If $L_1 = \{ab,b,varepsilon\}$ and $L_2 = \{b,dd,\varepsilon\}$ 
  then $L_1 L_2$ has all strings where the first
  string comes from $L_1$ and the second from $L_2$

\item So what is $\{a,aa\} \{bb,b\}$ ?

\item What is $\{ \} \{ \varepsilon\}$ ?

\item What is $\{ \} \{ a, aa\}$ ?

\item What is $ \{ a, aa\}  \{ \} $ ?

\item What is $\{ \varepsilon \} \{ a, aa\}  \{ \varepsilon \} \{ bb \} $ ?

\item For $L = \{ ab, b, \varepsilon\}$, we have 
  $L^2 = \{ab,b,\varepsilon\}  \{ab,b,\varepsilon\} $

\item For the above $L$, we have 
  $L^3 = \{ab,b,\varepsilon\}  \{ab,b,\varepsilon\} \{ab,b,\varepsilon\} $

\item For the above $L$, we have 
  $L^0 = \{ \varepsilon \}$ by definition (to allow the concat
  not to entirely disappear)!
\end{itemize}

\noindent Language union:

\begin{itemize}
\item  What is $\{ bb,cc \} \cup \{ a, aa\} $ ?
\end{itemize}

\noindent Kleene star of a language

\begin{itemize}
\item $L^* = L^0 \cup L^1 \cup ...$

\item i.e. $L^* = \cup_{k\ge 0} L^k $

\item This means $\emptyset^* = \{ \varepsilon \} $
\end{itemize}

\clearpage
\noindent Regular expressions

\begin{itemize}
\item Shorthands for (regular) languages

\item $\emptyset$ is an RE denoting language $\emptyset$

\item $\varepsilon$ is an RE denoting language $\{ \varepsilon\}$

\item $0$ is an RE denoting language $\{ 0 \}$

\item $1$ is an RE denoting language $\{ 1 \}$

\item For $R_1$ and $R_2$ as REs, $R_1 + R_2$ is an RE denoting...

\item For $R_1$ and $R_2$ as REs, $R_1 R_2$ is an RE denoting...

\item For $R$ as an RE, $(R)$ denotes...

\item For $R$ as an RE, $R^*$ denotes...

\item Do problem 2.1

Which of $\varepsilon, abba, bababb, baaaa$ are in the language of

   $(a+b)^* a b (a+b)^* $ ?


\item[]

\item {\bf Short break}

\item Discuss Assignment 2, introducing solving similar problems.

\end{itemize}

\end{LARGE}

\end{document}
