hw2.tex

\documentclass[a4paper,12pt]{article} % This defines the style of your paper

\usepackage[top = 2.5cm, bottom = 2.5cm, left = 2.5cm, right = 2.5cm]{geometry} 

\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}

\usepackage{multirow} % Multirow is for tables with multiple rows within one cell.
\usepackage{booktabs} % For even nicer tables.

\usepackage{graphicx} 

\usepackage{setspace}
\setlength{\parindent}{0in}

\usepackage{float}

\usepackage{fancyhdr}


\pagestyle{fancy} % With this command we can customize the header style.

\fancyhf{} % This makes sure we do not have other information in our header or footer.

\rhead{\footnotesize J. Klepl}

\cfoot{\footnotesize \thepage} 

\begin{document}

\thispagestyle{empty} % This command disables the header on the first page. 

\begin{center}
	{\Large \bf Homework 2 - $\exists\forall$}
	\vspace{2mm}

	{\bf Jiří Klepl}

\end{center}

\vspace{0.4cm}


\begin{quote}
	Ukažte, že jazyk $L$ je rozhodnutelný, právě když existují rozhodnutelné jazyky $A$ a $B$, pro které platí, že $L=\{x | (\exists y)[\left<x, y\right> \in A]\} = \{x | (\forall y)[\left<x,y\right> \in B]\}$
\end{quote}

\subsection*{''$\Rightarrow$``}

Nastavíme $A := \left<L, \{\lambda\}\right>$ a $B := \left<L,\Sigma^\star\right>$.
\footnote{$(\forall X, Y \subseteq \Sigma^\star)[\label{foot} \left< X, Y\right>$ je zkratka za $\{\left<\right.\} \cdot X \cdot \{,\} \cdot Y \cdot \{\left.\right>\}]$.}

$L$ je rozhodnutelný, tedy i $A$, a $B$ díky uzavřenosti rozhodnutelných jazyků na řetězení.

\subsection*{''$\Leftarrow$``}

Jazyky $A$ a $B$ jsou rozhodnutelné, tedy z uzavřenosti na průnik i $A \cap \left<\Sigma^\star, \Sigma^\star\right>$ a $B \cap \left<\Sigma^\star, \Sigma^\star\right>$ jsou regulární a dají nám stejnou definici $L$. Budeme tedy uvažovat tyto průniky jako původní $A$ a $B$.

Víme, že $A \subseteq \left<L,\Sigma^\star\right> \subseteq B$ a $L' = \{x | (\exists y)[\left<x, y\right> \in B']\} = \{x | (\forall y)[\left<x,y\right> \in A']\}$.

Tedy $(\forall x \in L')[\left<x,\right> \in A' \wedge \left<x,\right> \not\in A]$ a $(\forall x \in L)[\left<x,\right> \in B \wedge \left<x,\right> \not\in B']$.

Tedy problém jazyka $L$ je převoditelný na problém rozhodnutelného jazyka $B \setminus A'$ a tedy $L$ je rozhodnutelný. Mimochodem, to šlo vidět už v zadání.


\end{document}