Skip to content

Instantly share code, notes, and snippets.

@oenone oenone/seminar.tex Secret
Created Apr 29, 2019

Embed
What would you like to do?
Präsentation von Kellerautomaten im Rahmen einer Preäsentations-Übung
\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}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.