\documentclass[12pt]{article}
\usepackage{amssymb}
\usepackage{tikz}
\usetikzlibrary{arrows,automata}
\newcommand{\solution}{\bigskip\noindent\textcolor{red}{Solution: }}
\begin{document}

\begin{center}
\large
MATH 4LT/6LT3 Assignment \#5
\\



Due:  Friday, 21 November by 11:59pm.

\bigskip
\end{center}



\begin{enumerate}

\item  Determine if the following language is computable.  Justify your answer.
\begin{quote}
NON-BLANK  is equal to the set of strings $\ulcorner M \urcorner$ such that $M$ is a DTM that when started with an empty tape eventually writes a non-blank symbol on its tape.
\end{quote}

\item Exercise 2.10.31 from the textbook.

\item Exercise 2.10.38, parts 4 and 5, from the textbook.

\item Exercise 3.10.12 from the textbook.

\item A triangle of a graph $G$ is a set of three distinct vertices $a$, $b$, and $c$ of $G$ such that there are edges in $G$ between each pair of vertices.  Let
       \[
       T = \{\langle G \rangle\mid\mbox{$G$ is a  graph that has a triangle}\}.\]
         Show that $T$ is PTIME, i.e., demonstrate that there is an algorithm that decides if a given  graph has a triangle or not, and whose run time can be bounded by a polynomial in the number of vertices of $G$.

\end{enumerate}


The following  question is for students enrolled in MATH 6LT3.  Students in MATH 4LT3 can treat it as  a bonus question.

\begin{enumerate}
  \item[B1]
Let $A = \{\ulcorner M\urcorner\mid \mbox{$M$ is a DFA with $L(M) \ne \emptyset$}\}$, i.e., $A$ consists of the codes of all DFAs that accept at least one string.  Here the details of the coding scheme for DFAs are not important for the purpose of this question.  One can use a similar scheme to the one for coding DTMs. Show that $A$ is a computable language, and in fact that $A \in \mathcal{P}$, the class of polynomial-time solvable languages.  To show this you can informally describe an algorithm that solves this problem and provide a polynomial upper bound on its run-time, as a function of the size of the DFA.

\end{enumerate}

\end{document}

