summaryrefslogtreecommitdiff
path: root/presentation
diff options
context:
space:
mode:
authorPatrick Simianer <p@simianer.de>2010-05-25 01:37:07 +0200
committerPatrick Simianer <p@simianer.de>2010-05-25 01:37:07 +0200
commit71c88ab76351d215d96249194e369bb73ce63736 (patch)
tree0336382beb15b1aa719653bc8f180f7d65cfd85d /presentation
parentf8f3a94e6d9572bef0849b15752b81d0402bfc90 (diff)
g.tex
Diffstat (limited to 'presentation')
-rw-r--r--presentation/g.tex267
1 files changed, 267 insertions, 0 deletions
diff --git a/presentation/g.tex b/presentation/g.tex
new file mode 100644
index 0000000..8b32c8e
--- /dev/null
+++ b/presentation/g.tex
@@ -0,0 +1,267 @@
+% g.tex
+% Patrick Simianer <p@simianer.de>
+% 2010-05-24
+\documentclass{scrartcl}
+
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage[ngerman]{babel}
+\usepackage{lmodern}
+
+\usepackage{tikz}
+\usetikzlibrary{arrows,automata}
+
+
+\begin{document}
+
+
+$a*$\\
+
+\begin{tikzpicture}[shorten >=1pt,node distance=3cm,>=stealth',thick]
+ \tikzstyle{every state}=[draw=blue!50,very thick,fill=blue!20]
+
+ \node[state,initial] (A) {$\{2, 3\}$};
+ \node[state,accepting] (B) [below of=A] {$\{0, 1, 3\}$};
+
+ \path[->] (A) edge node {$\ \ \ \ a$} (B)
+ (B) edge [loop below] node {$a$} ();
+\end{tikzpicture}
+
+\begin{tikzpicture}[shorten >=1pt,node distance=3cm,>=stealth',thick]
+ \tikzstyle{every state}=[draw=blue!50,very thick,fill=blue!20]
+
+ \node[state,initial] (s2) {$2$};
+ \node[state,accepting] (s3) [right of=s2] {$3$};
+ \node[state] (s0) [below left of=s2] {$0$};
+ \node[state] (s1) [below left of=s3] {$1$};
+
+
+\path[->] (s2) edge node {$\epsilon$} (s3)
+ (s2) edge node {$a$} (s0)
+ (s0) edge [bend right] node {$\epsilon$} (s1)
+ (s1) edge [bend right] node {$a$} (s0)
+ (s1) edge node {$\epsilon$} (s3);
+
+\end{tikzpicture}
+
+
+
+\begin{tikzpicture}[shorten >=1pt,node distance=3cm,>=stealth',thick]
+ \tikzstyle{every state}=[draw=blue!50,very thick,fill=blue!20]
+
+ \node[state,initial] (s2) {$2$};
+ \node[state] (s0) [right of=s2] {$0$};
+ \node[state] (s1) [right of=s0] {$1$};
+ \node[state,accepting] (s3) [right of=s1] {$3$};
+
+
+\path[->] (s2) edge [bend right] node {$\epsilon$} (s3)
+ (s2) edge node {$\epsilon$} (s0)
+ (s0) edge node {$a$} (s1)
+ (s1) edge [bend right] node {$\epsilon$} (s0)
+ (s1) edge node {$\epsilon$} (s3);
+\end{tikzpicture}
+
+
+$(a|b)*$\\
+
+\begin{tikzpicture}[shorten >=1pt,node distance=2cm,>=stealth',thick]
+ \tikzstyle{every state}=[draw=blue!50,very thick,fill=blue!20]
+
+ \node[state,initial] (s6) {$6$};
+ \node[state] (s4) [right of=s6] {$4$};
+ \node[state] (s0) [above right of=s4] {$0$};
+ \node[state] (s2) [below right of=s4] {$2$};
+ \node[state] (s1) [right of=s0] {$1$};
+ \node[state] (s3) [right of=s2] {$3$};
+ \node[state] (s5) [below right of=s1] {$5$};
+ \node[state,accepting] (s7) [right of=s5] {$7$};
+
+\path[->] (s6) edge node {$\epsilon$} (s4)
+ (s4) edge node {$\epsilon$} (s0)
+ (s4) edge node {$\epsilon$} (s2)
+ (s0) edge node {$a$} (s1)
+ (s2) edge node {$b$} (s3)
+ (s1) edge node {$\epsilon$} (s5)
+ (s3) edge node {$\epsilon$} (s5)
+ (s5) edge node {$\epsilon$} (s4)
+ (s5) edge node {$\epsilon$} (s7)
+ (s6) edge [bend right] node {$\epsilon$} (s7);
+\end{tikzpicture}
+
+
+\begin{tikzpicture}[shorten >=1pt,node distance=4cm,>=stealth',thick]
+ \tikzstyle{every state}=[draw=blue!50,very thick,fill=blue!20]
+
+ \node[state,initial] (A) {$\{6,7,4,0,2\}$};
+ \node[state] (B) [below left of=A] {$\{1,5,7,4,0,2\}$};
+ \node[state,accepting] (C) [below right of=A] {$\{3,5,7,4,0,2\}$};
+
+
+\path[->] (A) edge node {$a$} (B)
+ (A) edge node {$b$} (C)
+ (B) edge [loop below] node {$a$} (B)
+ (C) edge [loop below] node {$b$} (C)
+ (B) edge [bend right] node {$b$} (C)
+ (C) edge [bend right] node {$a$} (B);
+\end{tikzpicture}
+
+$a*b|b*a$\\
+
+\begin{tikzpicture}[shorten >=1pt,node distance=3cm,>=stealth',thick]
+ \tikzstyle{every state}=[draw=blue!50,very thick,fill=blue!20]
+
+ \node[state,initial] (s12) {$12$};
+
+ \node[state] (s2) [above right of=s12] {$2$};
+ \node[state] (s3) [right of=s2] {$3$};
+ \node[state] (s0) [above of=s2] {$0$};
+ \node[state] (s1) [above of=s3] {$1$};
+ \node[state] (s4) [right of=s3] {$4$};
+ \node[state] (s5) [right of=s4] {$5$};
+
+ \node[state] (s8) [below right of=s12] {$8$};
+ \node[state] (s6) [below of=s8] {$6$};
+ \node[state] (s7) [right of=s6] {$7$};
+ \node[state] (s9) [right of=s8] {$9$};
+ \node[state] (s10) [right of=s9] {$10$};
+ \node[state] (s11) [right of=s10] {$11$};
+
+ \node[state,accepting] (s13) [below right of=s5] {$13$};
+
+\path[->]
+(s12) edge node {$\epsilon$} (s2)
+(s2) edge node {$\epsilon$} (s0)
+(s0) edge [bend right] node {$a$} (s1)
+(s1) edge [bend right] node {$\epsilon$} (s0)
+(s1) edge node {$\epsilon$} (s3)
+(s2) edge node {$\epsilon$} (s3)
+(s3) edge node {$\epsilon$} (s4)
+(s4) edge node {$b$} (s5)
+(s5) edge node {$\epsilon$} (s13)
+
+(s12) edge node {$\epsilon$} (s8)
+(s8) edge node {$\epsilon$} (s6)
+(s6) edge [bend right] node {$b$} (s7)
+(s7) edge [bend right] node {$\epsilon$} (s6)
+(s8) edge node {$\epsilon$} (s9)
+(s7) edge node {$\epsilon$} (s9)
+(s9) edge node {$\epsilon$} (s10)
+(s10) edge node {$a$} (s11)
+(s11) edge node {$\epsilon$} (s13);
+\end{tikzpicture}
+
+
+\begin{tikzpicture}[shorten >=1pt,node distance=5cm,>=stealth',thick]
+ \tikzstyle{every state}=[draw=blue!50,very thick,fill=blue!20]
+
+ \node[state,initial] (A) {$\{12,2,0,3,4,8,6,9,10\}$};
+
+ \node[state,accepting] (B) [above right of=A] {$\{1, 3, 4, 0, 11, 13\}$};
+ \node[state] (C) [right of=B] {$\{1, 3, 4, 0\}$};
+ \node[state,accepting] (D) [right of=C] {$\{5, 13\}$};
+
+ \node[state,accepting] (E) [below right of=A] {$\{7,9,10,6,5,13\}$};
+ \node[state,accepting] (F) [right of=E] {$\{7,9,10,6\}$};
+ \node[state,accepting] (G) [right of=F] {$\{11,13\}$};
+
+
+\path[->] (A) edge node {$a$} (B)
+ (B) edge [bend left] node {$b$} (D)
+ (B) edge node {$a$} (C)
+ (C) edge [loop below] node {$a$} (C)
+ (C) edge node {$b$} (D)
+
+ (A) edge node {$b$} (E)
+ (E) edge [bend right] node {$a$} (G)
+
+ (E) edge node {$b$} (F)
+ (F) edge [loop above] node {$b$} (F)
+ (F) edge node {$a$} (G);
+\end{tikzpicture}
+
+
+
+\begin{tikzpicture}[shorten >=1pt,node distance=3cm,>=stealth',thick]
+ \tikzstyle{every state}=[draw=blue!50,very thick,fill=blue!20]
+
+ \node[state,initial] (A) {};
+ \node[state,accepting] (B) [right of=A] {};
+
+ \path[->] (A) edge node {$a$} (B);
+\end{tikzpicture}\\
+
+\begin{tikzpicture}[shorten >=1pt,node distance=3cm,>=stealth',thick]
+ \tikzstyle{every state}=[draw=blue!50,very thick,fill=blue!20]
+
+ \node[state,initial] (A) {};
+ \node[state,accepting] (B) [right of=A] {};
+
+ \path[->] (A) edge node {$\epsilon$} (B);
+\end{tikzpicture}
+
+$ab$\\
+\begin{tikzpicture}[shorten >=1pt,node distance=3cm,>=stealth',thick]
+ \tikzstyle{every state}=[draw=blue!50,very thick,fill=blue!20]
+
+ \node[state,initial] (A) {};
+ \node[state,accepting] (B) [right of=A] {};
+ \node[state] (C) [right of=B] {};
+ \node[state,accepting] (D) [right of=C] {};
+
+ \path[->]
+(A) edge node {$a$} (B)
+(B) edge node {$\epsilon$} (C)
+(C) edge node {$b$} (D);
+\end{tikzpicture}
+
+
+
+$(a|b)$\\
+\begin{tikzpicture}[shorten >=1pt,node distance=3cm,>=stealth',thick]
+ \tikzstyle{every state}=[draw=blue!50,very thick,fill=blue!20]
+
+ \node[state,initial] (A) {};
+ \node[state] (B) [above right of=A] {};
+ \node[state] (C) [below right of=A] {};
+ \node[state,accepting] (D) [right of=B] {};
+ \node[state,accepting] (E) [right of=C] {};
+ \node[state,accepting] (F) [above right of=E] {};
+
+\path[->] (A) edge node {$\epsilon$} (B)
+(A) edge node {$\epsilon$} (C)
+
+(B) edge node {$a$} (D)
+(C) edge node {$b$} (E)
+
+
+(D) edge node {$\epsilon$} (F)
+(E) edge node {$\epsilon$} (F)
+;
+\end{tikzpicture}
+
+
+
+
+$a*$\\
+\begin{tikzpicture}[shorten >=1pt,node distance=3cm,>=stealth',thick]
+ \tikzstyle{every state}=[draw=blue!50,very thick,fill=blue!20]
+
+ \node[state,initial] (A) {};
+ \node[state] (B) [right of=A] {};
+ \node[state,accepting] (C) [right of=B] {};
+ \node[state,accepting] (D) [right of=C] {};
+
+ \path[->]
+(A) edge node {$\epsilon$} (B)
+(B) edge node {$a$} (C)
+(C) edge [bend right] node {$\epsilon$} (B)
+
+(C) edge node {$\epsilon$} (D)
+(A) edge [bend right] node {$\epsilon$} (D);
+
+\end{tikzpicture}
+
+
+\end{document}
+