Präsentation von Kellerautomaten im Rahmen einer Preäsentations-Übung

seminar.tex

\documentclass[12pt,xcolor={table,dvipsnames}]{beamer}

% fonts
\usepackage[T1]{fontenc}
\usepackage{textcomp}
\usepackage{mathptmx}
\usepackage[scaled=.90]{helvet}
\usepackage{courier}

% sprache
\usepackage[ngerman]{babel}
\usepackage[latin1]{inputenc}

% bilder
\usepackage{graphicx}
\usepackage{graphs}

% nützliches
\usepackage{tabularx}
\usepackage{booktabs}
\usepackage{multicol}

% beamer settings
\usetheme{Madrid}
\useinnertheme{rectangles}

% transparenz
\setbeamercovered{invisible}

\setbeamertemplate{mini frames}[box]
\setbeamertemplate{navigation symbols}{}

% margin
\setbeamersize{text margin left=2em,text margin right=2em}

%\setbeamertemplate{sections/subsections in toc}[square]
%\setbeamertemplate{bibliography item}[default]
%\setbeamertemplate{itemize items}[triangle]
%\setbeamertemplate{enumerate items}[square]
%\setbeamertemplate{blocks}[rounded][shadow=true]

\begin{document}

%Titelseite
\title{Kellerautomaten}
\subtitle{Seminar Technik}
\author{Julian Leyh}
\date{2007-12-04}
\institute[{Hochschule Mannheim}]{
  \inst{}Fachbereich Informatik
  Hochschule Mannheim}
\logo{\includegraphics[scale=0.3]{logo.png}}
\titlegraphic{\includegraphics[scale=0.5]{kellertitel.png}}

\begin{frame}[plain]
  \titlepage
\end{frame}

\begin{frame}
  \frametitle{Inhaltsverzeichnis}
  \tableofcontents
\end{frame}

\section{Automaten}
\begin{frame}
  \frametitle{Automaten}

  \begin{columns}
    \begin{column}{4cm}
      \begin{itemize}
        \item<1-> Endliche Automaten
        \vspace{1.5cm}
        \item<2-> \alert<4>{Kellerautomat}
        \vspace{1.5cm}
        \item<3-> Turingmaschine
      \end{itemize}
    \end{column}
    \begin{column}{7cm}
       \only<1>{\includegraphics[scale=0.5]{ea.png}}
       \only<2,4>{\includegraphics[scale=0.3]{Kellerautomat.png}}
       \only<3>{\includegraphics[scale=0.7]{Turingmaschine.png}}
    \end{column}
  \end{columns}
\end{frame}

\section{Kellerautomaten}
\begin{frame}
  \frametitle{Kellerautomaten}

  \begin{block}{Kellerautomaten}
    sind nichtdeterministische {\em endliche Automaten}, die über einen {\em Kellerspeicher (Stack)} verfügen.
  \end{block}

  \begin{figure}
    \includegraphics[scale=0.3]{Kellerautomat.png}
  \end{figure}
\end{frame}

\begin{frame}
  \frametitle{Kellerspeicher (Stack)}

  \begin{columns}
    \begin{column}{5cm}
      \begin{itemize}
        \item<1-> Push
        \vspace{2cm}
        \item<3-> Pop
        \vspace{2cm}
        \item<5-> Top
      \end{itemize}
    \end{column}
    \begin{column}{6cm}
      \only<1>{\includegraphics[scale=0.4]{Push.png}}\only<2>{\includegraphics[scale=0.4]{Push2.png}}\only<3>{\includegraphics[scale=0.4]{Pop.png}}\only<4>{\includegraphics[scale=0.4]{Pop2.png}}\only<5>{\includegraphics[scale=0.4]{Top.png}}
    \end{column}
  \end{columns}
\end{frame}

\section{Beispiel}
\begin{frame}
  \frametitle{Kellerautomaten Beispiel}

  \begin{Beispiel}
    Eingabealphabet $\Sigma = \{a, b\}$ \pause

    Zustände: $Q = \{q_0, q_1, q_2\}$ (Startzustand: $q_0$, Endzustand: $q_2$) \pause

    Kelleralphabet: $\Gamma = \{\#, a\}$ (Kelleranfangssymbol: $\#$) \pause

    Zustandsüberführungsfunktion $\delta$: \pause

    \begin{tabular}{c c c @{$\rightarrow$} c c}
       Zustand & Eingabe & Keller & Zustand & Operation \\
       $q_0$ & $a$  & $\#$ & $q_0$ & $push(a)$ \\
       $q_0$ & $a$  & $a$  & $q_0$ & $push(a)$ \\
       $q_0$ & $b$  & $a$  & $q_1$ & $pop$ \\
       $q_1$ & $b$  & $a$  & $q_1$ & $pop$ \\
       $q_1$ & $\$$ & $\#$ & $q_2$ & ---
    \end{tabular}
  \end{Beispiel}
\end{frame}

\begin{frame}
  \frametitle{Kellerautomaten Beispiel}

  \begin{columns}
    \begin{column}{8cm}
    \only<1>{\includegraphics[scale=0.4]{beispiel_01.png}}
    \only<2>{\includegraphics[scale=0.4]{beispiel_01_2.png}}
    \only<3>{\includegraphics[scale=0.4]{beispiel_02.png}}
    \only<4>{\includegraphics[scale=0.4]{beispiel_02_2.png}}
    \only<5>{\includegraphics[scale=0.4]{beispiel_03.png}}
    \only<6>{\includegraphics[scale=0.4]{beispiel_03_2.png}}
    \only<7>{\includegraphics[scale=0.4]{beispiel_04.png}}
    \only<8>{\includegraphics[scale=0.4]{beispiel_04_2.png}}
    \only<9>{\includegraphics[scale=0.4]{beispiel_05.png}}
    \only<10>{\includegraphics[scale=0.4]{beispiel_05_2.png}}
    \only<11>{\includegraphics[scale=0.4]{beispiel_06.png}}
    \only<12>{\includegraphics[scale=0.4]{beispiel_06_2.png}}
    \only<13>{\includegraphics[scale=0.4]{beispiel_07.png}}
    \only<14>{\includegraphics[scale=0.4]{beispiel_07_2.png}}
    \end{column}
    \begin{column}{2cm}
      \alert<0>{\only<1-2>{$\delta ( q_0, a, \# ) \rightarrow ( q_0, push(a) )$}
      \only<3-4>{$\delta ( q_0, a, a ) \rightarrow ( q_0, push(a) )$}
      \only<5-6>{$\delta ( q_0, a, a ) \rightarrow ( q_0, push(a) )$}
      \only<7-8>{$\delta ( q_0, b, a ) \rightarrow ( q_1, pop )$}
      \only<9-10>{$\delta ( q_1, b, a ) \rightarrow ( q_1, pop )$}
      \only<11-12>{$\delta ( q_1, b, a ) \rightarrow ( q_1, pop )$}
      \only<13-14>{$\delta ( q_1, \$, \# ) \rightarrow ( q_2, - )$}
      }
    \end{column}
  \end{columns}
\end{frame}

\section{Sprache}
\begin{frame}
  \frametitle{Die Sprache des Kellerautomaten}

  \begin{itemize}
    \item Sprache = Akzeptierte Worte des Automaten
    \item Kellerautomat definiert kontextfreie Sprachen
    \item Sprache unseres Beispiel-Automats: $L = \{a^nb^n | n \ge 1\}$
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Grammatik des Kellerautomaten}

  \begin{itemize}
    \item kontextfreie Grammatik
    \item Grammatik unseres Beispiel-Automats: $S \rightarrow aXb, X \rightarrow aXb, X \rightarrow \epsilon$
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Grenzen der Kellerautomaten}

  \begin{itemize}
    \item kontextsensitive Sprachen
    \item allgemeine Sprachen
    \item z.B. $L = \{a^nb^nc^n | n \ge 1\}$
  \end{itemize}
\end{frame}

\section{Anwendung}
\begin{frame}
  \frametitle{Anwendungen des Kellerautomaten}

  \begin{itemize}
    \item Klammerausdrücke
    \item Parser
    \item Rekursion
    \item Java VM
    \item Programmiersprache ,,Forth''
    \item FPU bei 32-Bit x86-Architektur
  \end{itemize}
\end{frame}

\section{Abwandlungen}
\begin{frame}
  \frametitle{Abwandlungen des Kellerautomaten}

  \begin{itemize}
    \item Deterministische Kellerautomaten
    \vspace{1cm}
    \item Zweikellerautomaten
  \end{itemize}
\end{frame}

\begin{frame}
  \begin{block}{}
    \begin{center}
      \alt<2>{Vielen Dank für die Aufmerksamkeit!}{Noch fragen?}
    \end{center}
  \end{block}
\end{frame}

\end{document}