\documentclass[12pt]{article}
\usepackage[spanish,es-tabla]{babel}
\usepackage[latin1]{inputenc}
\usepackage{hyperref}
\usepackage{texdraw}
\usepackage{multicol}
\usepackage{fancyheadings}
\usepackage{theorem}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{color}
\usepackage{xcolor}

\usepackage[cal=boondox,scr=boondoxo]{mathalfa}
\usepackage{oldgerm}
\usepackage{euscript}
\usepackage{rotating}
\usepackage{enumerate}
\usepackage{textpos}
\usepackage{fge}
\usepackage{tikz-cd}
\usepackage{tikz}
\usetikzlibrary{babel,automata,positioning}
\tikzcdset{scale cd/.style={every label/.append style={scale=#1}, cells={nodes={scale=#1}}}}


\definecolor{processblue}{cmyk}{0.96,0,0,0}

{\theorembodyfont{\rmfamily} \newtheorem{teo}{Teorema}}
{\theorembodyfont{\rmfamily} \newtheorem{obs}{Observaci\'on}}
{\theorembodyfont{\rmfamily} \newtheorem{coro}{Corolario}}
{\theorembodyfont{\rmfamily} \newtheorem{lema}{Lema}}
{\theorembodyfont{\rmfamily} \newtheorem{prop}{Proposici\'on}}
{\theorembodyfont{\rmfamily} \newtheorem{defi}{Definici\'on}}
{\theorembodyfont{\rmfamily} \newtheorem{prob}{Problema}}
{\theorembodyfont{\rmfamily} \newtheorem{ejer}{Ejercicio}}
{\theorembodyfont{\rmfamily} \newtheorem{ejem}{Ejemplo}}

\newcommand{\find}[0]{\hfill $\blacksquare$}
\newcommand{\fine}[0]{\hfill $\Box$}
\newcommand{\findef}[0]{\noindent\hrulefill}
\newcommand{\derms}[0]{\overset{*}{\Rightarrow}}


\def\proof{\noindent{\textbf{Demostraci\'on}}\\}
\def\endproof{\hfill{\ensuremath\square}}
\def\refname{Referencias}
\def\abstractname{Resumen}

\title{Documento de ejemplo para reportar tareas \\
Lenguajes Formales y Autómatas \\
Licenciatura en Ciencias de la Computación o \\
Maestría en Ciencias de la Computación}
\author{José de Jesús Lavalle Martínez}
\date{}

\begin{document}
\maketitle

\begin{abstract}
Escribir brevemente qué se está reportando y cuál es su propósito.
\end{abstract}

\section{Nombre de la primera sección}
Desarrollar el discurso correspondiente al nombre de la primera sección, por ejemplo: 

\section{Nombre de la segunda sección}
Desarrollar el discurso correspondiente al nombre de la segunda sección, por ejemplo:

\section{Conclusiones}
Escribir dos o tres conclusiones sobre el trabajo desarrollado con respecto al propósito establecido en el resumen.

\section{Otros ejemplos}
\begin{ejem}\label{eje4}
Considere la gramática
\[
G = (\{S\}, \{a, b\}, S, P)
\]
con $P$ dado por
\begin{align*}
S & \rightarrow aSb, \\
S & \rightarrow \lambda.
\end{align*}
Entonces
\[
S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aabb,
\]
así que podemos escribir
\[
S \derms aabb.
\]
La cadena $aabb$ es una oración en el lenguaje generado por $G$, mientras que $aaSbb$ es una forma oracional.

Una gramática $G$ define completamente a $L(G)$, pero puede que no sea fácil obtener una descripción muy explícita del lenguaje a partir de la gramática. Aquí, sin embargo, la respuesta es bastante clara. No es difícil conjeturar que
$$L(G) = \{a^nb^n; n \geq 0\},$$
y es fácil probarlo. Si notamos que la regla $S \rightarrow aSb$ es recursiva, se sugiere inmediatamente una demostración por inducción. Primero mostramos que todas las formas oracionales deben tener la forma
\begin{equation}\label{eq1.7}
w_i = a^iSb^i.
\end{equation}
Suponga que (\ref{eq1.7}) se cumple para todas las formas oracionales $w_i$ de longitud $2i + 1$ o menos. Para obtener otra forma oracional (que no es una oración), solo podemos aplicar la producción $S \rightarrow aSb$. Esto nos da
\[
a^iSb^i \Rightarrow a^{i+1}Sb^{i+1},
\]
de modo que toda forma oracional de longitud $2i + 3$ también tiene la forma (\ref{eq1.7}). Dado que (\ref{eq1.7}) es obviamente cierto para $i = 1$, se cumple por inducción para todo $i$. Finalmente, para obtener una oración, debemos aplicar la producción $S \rightarrow \lambda$, y vemos que
\[
S \derms a^nSb^n \Rightarrow a^nb^n
\]
representa todas las posibles derivaciones. Por tanto, $G$ sólo puede derivar cadenas de la forma $a^nb^n$.

También tenemos que demostrar que se pueden derivar todas las cadenas de esta forma. Esto es fácil; simplemente aplicamos $S \rightarrow aSb$ tantas veces como sea necesario, seguido de $S \rightarrow \lambda$.
\fine
\end{ejem}

\begin{ejem}\label{eje7}
Considere la gramática $G_1 = (\{A, S\}, \{a, b\}, S, P_1)$, con $P_1$ que consta de las producciones
\begin{align*}
S & \rightarrow  aAb | \lambda, \\
A & \rightarrow aAb | \lambda.
\end{align*}
Aquí presentamos una notación abreviada conveniente en la que varias reglas de producción con los mismos lados izquierdos se escriben en la misma línea, con los lados derechos alternativos separados por $|$. En esta notación $S \rightarrow aAb | \lambda$ representa las dos producciones $S \rightarrow aAb$ y $S \rightarrow \lambda$.

Esta gramática es equivalente a la gramática $G$ del ejemplo \ref{eje4}. La equivalencia es fácil de probar mostrando que
$$L(G_1)=\{a^nb^n: n \geq 0\}.$$
\fine
\end{ejem}

\section{Como se produjo la tarea}
\begin{enumerate}
\item ¿Cuántas subcadenas $aab$ hay en $ww^Rw$, donde $w = aabbab$?
\item Use inducción sobre $n$ para demostrar que $|u^n| = n|u|$ para todas las cadenas $u$ y para todo $n$.
\item El reverso de una cadena, introducido informalmente anteriormente, se puede definir con mayor precisión mediante las reglas recursivas
\begin{align*}
a^R &= a, \\
(wa)^R &= aw^R,
\end{align*}
para todo $a \in \Sigma$, $w \in \Sigma^*$. Use esto para demostrar que
$$(uv)^R = v^Ru^R,$$
para todo $u, v \in \Sigma^+$.
\item Sea $L = \{ab, aa, baa\}$. ¿Cuáles de las siguientes cadenas están en $L^*: abaabaaabaa, aaaabaaaa, baaaaabaaaab, baaaaabaa$? ¿Qué cadenas están en $L^4$?
\item Sea $\Sigma = \{a, b\}$ y $L = \{aa, bb\}$. Utilice la notación de conjuntos para describir $\overline{L}$.
\item Demuestre que 
$$(L_1L_2)^R = L_2^RL_1^R$$
para todos los lenguajes $L_1$ y $L_2$.
\item Encuentre una gramática para el lenguaje $L = \{a^n, \text{ donde n es par}\}$.
\item Dé una descripción sencilla del lenguaje generado por la gramática con producciones
\begin{align*}
S & \rightarrow aaA, \\
A & \rightarrow bS, \\
S & \rightarrow \lambda.
\end{align*}
\item Encuentre tres cadenas en el lenguaje generado por 
$$S \rightarrow aSb | bSa | a.$$
\item Complete los argumentos en el Ejemplo \ref{eje7}, mostrando que $L(G_1)$ en efecto genera el lenguaje dado en el Ejemplo \ref{eje4}.
\end{enumerate}

\section{La manera de dibujar autómatas}
\begin{center}
\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto, every node/.style={scale=1}, color = blue, text = black] 
   \node[state,initial] (q_0)   {$q_0$}; 
   \node[state] (q_1) [right=of q_0] {$q_1$}; 
   \node[state] (q_2) [below=of q_1] {$q_3$}; 
   \node[state,accepting](q_3) [right=of q_1] {$q_2$};
    \path[->] 
    (q_0) edge [loop above] node {$a$} (q_0)
    (q_1) edge  node  {$a$} (q_2)
          edge node {$b$} (q_3)
    (q_2) edge  node {$b$} (q_0);
\end{tikzpicture}

\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto, every node/.style={scale=1}, color = blue, text = black] 
\node[state, initial] (q1) {$q_1$};
\node[state, accepting, right of=q1] (q2) {$q_2$};
\node[state, right of=q2] (q3) {$q_3$};
\draw (q1) edge[loop above] node{0} (q1)
(q1) edge[above] node{1} (q2)
(q2) edge[loop above] node{1} (q2)
(q2) edge[bend left, above] node{0} (q3)
(q3) edge[bend left, below] node{0, 1} (q2);
\end{tikzpicture}
\end{center}
\end{document}