Skip to content

Instantly share code, notes, and snippets.

@maufirf

maufirf/tba112_assign01_1313617014.tex

Last active April 15, 2020 04:41
Show Gist options
  • Save maufirf/544152e623aac9f6138d9aba86150c36 to your computer and use it in GitHub Desktop.
Save maufirf/544152e623aac9f6138d9aba86150c36 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
tba112_assign01_1313617014.tex
%--------------------
% Packages
% -------------------
\documentclass[11pt,a4paper]{article}
\usepackage[utf8x]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage{gentium}
%\usepackage{mathptmx} % Use Times Font
\usepackage[T1]{fontenc} %https://tug.org/FontCatalogue/computermodern/
\usepackage{lmodern} %https://tex.stackexchange.com/questions/10706/pdftex-error-font-expansion-auto-expansion-is-only-possible-with-scalable
\usepackage{amsmath} %https://tex.stackexchange.com/questions/41035/what-is-causing-undefined-control-sequence
\usepackage{url} %https://tex.stackexchange.com/questions/173115/how-to-add-text-after-a-forward-slash
\usepackage{multicol} %https://tex.stackexchange.com/questions/194426/split-itemize-into-multiple-columns
\usepackage[pdftex]{graphicx} % Required for including pictures
\usepackage[swedish]{babel} % Swedish translations
\usepackage[pdftex,linkcolor=black,pdfborder={0 0 0}]{hyperref} % Format links for pdf
\usepackage{calc} % To reset the counter in the document after title page
\usepackage{enumitem} % Includes lists
\frenchspacing % No double spacing between sentences
\linespread{1.2} % Set linespace
\usepackage[a4paper, lmargin=0.1666\paperwidth, rmargin=0.1666\paperwidth, tmargin=0.1111\paperheight, bmargin=0.1111\paperheight]{geometry} %margins
%\usepackage{parskip}
\usepackage[all]{nowidow} % Tries to remove widows
\usepackage[protrusion=true,expansion=true]{microtype} % Improves typography, load after fontpackage is selected
%https://tex.stackexchange.com/questions/20784/which-package-can-be-used-to-draw-automata
\usepackage{tikz}
\usetikzlibrary{automata,positioning}
\title{Language \& Automata Theory 112 - Assignment 1}
\date{2020\\ April}
\author{Muhammad Aufi Rayesa Frandhana (1313617014)\\ 2017 Computer Science, Jakarta State University}
%https://tex.stackexchange.com/questions/51762/how-do-you-effectively-debug-overfull-hbox-warnings
\showboxdepth=\maxdimen
\showboxbreadth=\maxdimen
%-----------------------
% Set pdf information and add title, fill in the fields
%-----------------------
\hypersetup{
pdfsubject = {},
pdftitle = {},
pdfauthor = {}
}
%-----------------------
% Begin document
%-----------------------
\begin{document} %All text i dokumentet hamnar mellan dessa taggar, allt ovanför är formatering av dokumentet
\maketitle
\section{Answers}
\subsection*{Question 1}
\begin{flushleft}
\textbf{Q:} Which of the strings 0001, 01101, 00001101 are accepted by the dfa in Figure 2.1?
\end{flushleft}%
\begin{flushleft}
\textbf{A:} All of them are accepted in the said dfa.
\end{flushleft}%
\subsection*{Question 2}
\begin{flushleft}
\textbf{Q:} Translate the graph in Figure 2.5 into $\delta-$ notation.
\end{flushleft}%
\begin{flushleft}
\textbf{A:} with $w \in \Sigma^{*}$
\begin{multicols}{2}
\begin{itemize}
\item $\delta(\lambda,1)=\lambda$
\item $\delta(\lambda,01)=\lambda$
\item $\delta(\lambda,00)=00$
\item $\delta(00,0)=00$
\item $\delta(00,1)=001$
\item $\delta(\lambda,001)=001$
\item $\delta(001,w)=001$
\end{itemize}
\end{multicols}
\end{flushleft}%
\subsection*{Question 3}
\begin{flushleft}
\textbf{Q:} For $\Sigma = \{a, b\}$, construct dfa’s that accept the sets consisting of the given rules
\end{flushleft}%
\begin{flushleft}
\textbf{A:}
\renewcommand{\labelenumi}{(\alph{enumi})} %https://www.overleaf.com/learn/latex/lists
\begin{enumerate}
\item all strings of even length.\\
\begin{tikzpicture}[shorten >=1pt, node distance=2cm,on grid,auto]
\node[state,initial,accepting] (even) {even};
\node[state] (odd) [right=of even] {odd};
\path[->]
(even) edge[bend left] node {a,b} (odd)
(odd) edge[bend left] node {a,b} (even);
\end{tikzpicture}
\item all strings of length greater than 5.\\
\begin{tikzpicture}[shorten >=1pt, node distance=2cm,on grid,auto]
\node[state,initial] (q_0) {$q_0$};
\node[state] [right=of q_0] (q_1) {$q_1$};
\node[state] [right=of q_1] (q_2) {$q_2$};
\node[state] [right=of q_2] (q_3) {$q_3$};
\node[state] [right=of q_3] (q_4) {$q_4$};
\node[state,accepting] [right=of q_4] (q_accept) {$q_{accept}$};
\path[->]
(q_0) edge node {a,b} (q_1)
(q_1) edge node {a,b} (q_2)
(q_2) edge node {a,b} (q_3)
(q_3) edge node {a,b} (q_4)
(q_4) edge node {a,b} (q_accept)
(q_accept) edge [loop right] node {a,b} (q_accept);
\end{tikzpicture}
\item all strings with an even number of $a$’s.\\
\begin{tikzpicture}[shorten >=1pt, node distance=2cm,on grid,auto]
\node[state,initial,accepting] (evena) {even $a$'s};
\node[state] [right=of evena] (odda) {odd $a$'s};
\path[->]
(evena) edge[bend left] node {a} (odda)
edge [loop above] node {b} ()
(odda) edge[bend left] node {a} (evena)
edge [loop above] node {b} ();
\end{tikzpicture}
\item all strings with an even number of $a$’s and an odd number of $b$’s.\\
\begin{tikzpicture}[shorten >=1pt, node distance=2cm,on grid,auto]
\node[state,initial] (eaeb) {$a_0$,$b_0$};
\node[state] [right=of eaeb] (oaeb) {$a_1$,$b_0$};
\node[state,accepting] [below=of eaeb] (eaob) {$a_0$,$b_1$};
\node[state] [below=of oaeb] (oaob) {$a_1$,$b_1$};
\path[->]
(eaeb) edge[bend left] node {a} (oaeb)
edge[bend left] node {b} (eaob)
(oaeb) edge[bend left] node {a} (eaeb)
edge[bend left] node {b} (oaob)
(eaob) edge[bend left] node {a} (oaob)
edge [bend left] node{b} (eaeb)
(oaob) edge[bend left] node {a} (eaob)
edge[bend left] node {b} (oaeb);
\end{tikzpicture}
\end{enumerate}
\end{flushleft}%
\subsection*{Question 5}
\begin{flushleft}
\textbf{Q:} Give dfa’s for the languages given.
\end{flushleft}%
\begin{flushleft}
\textbf{A:}
\renewcommand{\labelenumi}{(\alph{enumi})} %https://www.overleaf.com/learn/latex/lists
\begin{enumerate}
\item $L=\{ab^{4}wb^{2}:w\in{\{a,b}^{*}\}\}$\\
\begin{tikzpicture}[shorten >=1pt, node distance=2cm,on grid,auto]
\node[state,initial] (q_0) {$q_0$};
\node[state] [below=of q_0] (q_1) {$q_1$};
\node[state] [right=of q_0] (q_2) {$q_2$};
\node[state] [right=of q_2] (q_3) {$q_3$};
\node[state] [right=of q_3] (q_4) {$q_4$};
\node[state] [right=of q_4] (q_5) {$q_5$};
\node[state] [right=of q_5] (q_6) {$q_6$};
\node[state,accepting] [right=of q_6] (q_7) {$q_7$};
\path[->]
(q_0) edge [bend left] node {a} (q_2)
edge node {b} (q_1)
(q_1) edge [loop right] node {a,b} ()
(q_2) edge [bend left] node {a} (q_0)
edge [bend left] node {b} (q_3)
(q_3) edge [bend left] node {a} (q_2)
edge [bend left] node {b} (q_4)
(q_4) edge [bend left] node {a} (q_3)
edge [bend left] node {b} (q_5)
(q_5) edge [bend left] node {a} (q_4)
edge [bend left] node {b} (q_6)
(q_6) edge [loop below] node {a} ()
edge [bend left] node {b} (q_7)
(q_7) edge [bend left] node {a} (q_6)
edge [loop below] node {b} ();
\end{tikzpicture}
\item $L=\{ab^{n}a^{m}:n\geq3,m\geq2\}$\\
\begin{tikzpicture}[shorten >=1pt, node distance=2cm,on grid,auto]
\node[state,initial] (q_0) {$q_0$};
\node[state] [below=of q_0] (q_1) {$q_1$};
\node[state] [right=of q_0] (q_2) {$q_2$};
\node[state] [right=of q_2] (q_3) {$q_3$};
\node[state] [right=of q_3] (q_4) {$q_4$};
\node[state] [right=of q_4] (q_5) {$q_5$};
\node[state,accepting] [right=of q_5] (q_6) {$q_6$};
\path[->]
(q_0) edge[bend left] node {a} (q_2)
edge node {b} (q_1)
(q_1) edge[loop right] node {a,b} ()
(q_2) edge[bend left] node {a} (q_0)
edge[bend left] node {b} (q_3)
(q_3) edge[bend left] node {a} (q_2)
edge[bend left] node {b} (q_4)
(q_4) edge[bend left] node {a} (q_3)
edge[bend left] node {b} (q_5)
(q_5) edge[bend left] node {a} (q_6)
edge[loop below] node {b} ()
(q_6) edge[loop below] node {a} ()
edge[bend left] node {a} (q_5);
\end{tikzpicture}
\item $L=\{w_{1}abbw_{2}:w_{1}\in\{a,b\}^{*},w_{2}\in\{a,b\}^{*}\}$\\
\begin{tikzpicture}[shorten >=1pt, node distance=2cm,on grid,auto]
\node[state,initial] (q0) {$q_0$};
\node[state] [right=of q_0] (q_1) {$q_1$};
\node[state] [right=of q_1] (q_2) {$q_2$};
\node[state] [right=of q_2] (q_3) {$q_3$};
\node[state,accepting] [right=of q_3] (q_4) {$q_4$};
\path[->]
(q_0) edge[bend left] node {a,b} (q_1)
(q_1) edge[bend left] node {a} (q_2)
edge[bend left] node {b} (q_0)
(q_2) edge[bend left] node {a} (q_1)
edge[bend left] node {b} (q_3)
(q_3) edge[bend left] node {a} (q_2)
edge[bend left] node{b} (q_4)
(q_4) edge[loop right] node {a,b} ();
\end{tikzpicture}
\item $L=\{ba^{n}:n\geq1,n\neq4\}$\\
\begin{tikzpicture}[shorten >=1pt, node distance=2cm,on grid,auto]
\node[state,initial] (q0) {$q_0$};
\node[state] [right=of q_0] (q_2) {$q_2$};
\node[state,accepting] [right=of q_2] (q_3) {$q_3$};
\node[state,accepting] [right=of q_3] (q_4) {$q_4$};
\node[state] [below=of q_4] (q_1) {$q_1$};
\node[state,accepting] [right=of q_4] (q_5) {$q_5$};
\node[state] [right=of q_5] (q_6) {$q_6$};
\node[state,accepting] [right=of q_6] (q_7) {$q_7$};
\path[->]
(q_0) edge[bend right] node {a} (q_1)
edge[bend left] node {b} (q_2)
(q_2) edge[bend left] node {a} (q_3)
edge[bend left] node {b} (q_0)
(q_3) edge[bend left] node {a} (q_4)
edge[bend left] node {b} (q_2)
(q_4) edge[bend left] node {a} (q_5)
edge node {b} (q_1)
(q_1) edge[loop below] node {a,b} ()
(q_5) edge node {a,b} (q_6)
(q_6) edge[bend left] node {a} (q_7)
edge[bend left] node {b} (q_1)
(q_7) edge[loop below] node {a} ()
edge[bend left] node{b} (q_6);
\end{tikzpicture}
\end{enumerate}
\end{flushleft}%
\begin{flushleft}
\textit{\textbf{POWER OF ATTORNEY NOTICE:} I have not being invited to our Microsoft Teams room due to lack of information if we actually have a Teams room, and by the time I realize we have one, the invitation link is already expired, therefore I gave the power to my colleague, Fathurrahman Ikhsan, to submit through his Microsoft account. In the meantime, I request to be invited into our Microsoft Teams room. I use the email issued by college to use Microsoft Teams: AufiRayesa\_Ilkom17@mahasiswa.unj.ac.id\newline \newline This \LaTeX{} source code can be found on \path{https://gist.github.com/parampaa2/544152e623aac9f6138d9aba86150c36}}
\end{flushleft}
\end{document}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment