% -----------------------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}{Bonus Homework No.1} % 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}\\
By {\sf S$\omega$S}, we denote the monadic second-order theory of $\mathcal{T}_\omega  = (\mathbb{N}^*, \{S_i(x) \}_{i \in \mathbb{N}}, \subset, \preccurlyeq)$, where $S_i(w) = w\hat{\hspace{4pt}}i$ ($i \in \mathbb{N}$),
$\subset$ is the prefix and $\preccurlyeq$ is the lexicographic order.


Now let $f: \mathbb{N}^* \to \{ 0, 1 \}^*$ be $$f(n_0 n_1\dots n_{k-1}) = 0^{n_0} 1 0^{n_1} 1 \cdots 1 0^{n_{k-1}} 1, \quad \text{and } f(\epsilon) = \epsilon. $$
Letting $D$ be the range of $f$, we have $\mathcal{D} = (D, \{S^D_i(x) \}_{i \in \mathbb{N}}, \subset^D, \preccurlyeq^D) \cong {\mathcal T_\omega}$.
\bigskip 

Then show that ${\mathcal D}$ is S2S-definable (Note: $\subset$ and $\preccurlyeq$ cannot be defined in $(\mathbb{N}^*, \{S_i(x) \}_{i \in \mathbb{N}})$). From this, derive that {\sf S$\omega$S} is decidable.
\bigskip

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

\vspace{5cm}



\vspace{8cm}






\end{document}




