%
% Assignment 4c for CS3530 Computational Theory:
% Turing Machines
% Fall 2024
%
% Problems taken from Sipser
%

\documentclass{article}

\usepackage[margin=1in]{geometry}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{ae,aecompl}
\usepackage{enumerate}
\usepackage{multicol}

% skip for paragraphs, don't indent
\parskip 6pt plus 1pt
\parindent=0pt
\raggedbottom

% a list environment with no bullets or numbers
\newenvironment{indentlist}{\begin{list}{}{\addtolength{\itemsep}{0.5\baselineskip}}}{\end{list}}

\begin{document}
\begin{center}
\textbf{\Large CS 3530: Assignment 4c} \\[2mm]
Fall 2024
\end{center}

\raggedright


\section*{Problem 4.12 (10 points)}

\subsection*{Problem}

Let $A = \{ \langle R,S \rangle | R $ and $ S $ are regular expressions and $ L(R) \subseteq L(S) \}$.  Show that $A$ is decidable.

\subsection*{Solution}



\section*{Problem 4.15 (10 points)}

\subsection*{Problem}

Let $A = \{ \langle R \rangle | R $ is a regular expression describing a language containing at least one string $w$ that has $111$ as a substring (i.e., $w = x111y$ for some $x$ and $y$) $ \}$.  Show that $A$ is decidable.

\subsection*{Solution}




\end{document}
