% -----------------------acknowledge for overleaf and designer of this template-----------------------
\documentclass[12pt]{exam}
\usepackage{amsthm}
\usepackage{libertine}
\usepackage[utf8]{inputenc}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb}
\usepackage{multicol}
\usepackage[shortlabels]{enumitem}
\usepackage{siunitx}
\usepackage{cancel}
\usepackage{graphicx}
\usepackage{pgfplots}
\usepackage{listings}
\usepackage[all]{xy}


%command 
\newcommand{\code}[1]{\ulcorner #1 \urcorner}
%\newcommand{\CE}{$\mathsf{CE}$}
\newcommand{\Ce}{$\mathsf{CE}$~}
\newcommand{\II}{{\sf I \,}}
\newcommand{\ol}[1]{\overline{#1}}

\newcommand{\la}{\leftarrow}
\newcommand{\ra}{\rightarrow}
\newcommand{\lr}{\leftrightarrow}
\newcommand{\La}{\Leftarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\LR}{\Leftrightarrow}

% automata
%\usepackage{tikz}
%\usetikzlibrary{automata, positioning, arrows}


\pgfplotsset{width=10cm,compat=1.9}
\usepgfplotslibrary{external}
\tikzexternalize

\newcommand{\class}{\Large Logic and Computation II, Spring 2023 } % This is the name of the course 
\newcommand{\examnum}{Homework No.13} % This is the index of the homework
\newcommand{\examdate}{} % This is the due date
\newcommand{\examname}{Name:    } % Your name here





\begin{document}
\pagestyle{plain}
\thispagestyle{empty}

\noindent
\begin{tabular*}{\textwidth}{l @{\extracolsep{\fill}} r @{\extracolsep{8pt}} l}
\textbf{\class} & & \textit{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}\\
&&\\
\textbf{\examnum} & &\textit{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}\\ 
\textbf{\examdate} &&\\
\textbf{\examname} &&\\
\end{tabular*}\\
\rule[2ex]{\textwidth}{2pt}
% ---

\noindent \textbf{Problem 1}\\
Prove that $L = \{ u^\omega : u \in \{0,1\}^+ \}$ is not an 
$\omega$-regular language.
\bigskip

\noindent\underline{\textsf{Solution:}}

\vspace{5cm}


\noindent \textbf{Problem 2}\\
(1) Express the following predicates with {\sf S1S} formulas.
\begin{itemize}
\item [(a)] $X$ is the set of even numbers.
\item [(b)] $X$ is finite with even number of elements.
\end{itemize}
\bigskip 

\noindent (2) Explain why ``$X$ and $Y$ have the same cardinality'' cannot be expressed by an {\sf S1S} formula.
\bigskip

\noindent\underline{\textsf{Solution:}}

\vspace{8cm}






\end{document}




