\documentclass{scrartcl}
\usepackage[margin=1in, left=0.5in, right=0.5in]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{fancyhdr}
\usepackage{mathtools}
\fancyhead[R]{\textsc{Langage formels, calculabilité et complexité}}
\fancyhead[L]{TD5} % except the center
\fancyfoot{} % except the center
\fancyfoot[L]{louis.jachiet@ens.fr}
\fancyfoot[R]{26 octobre 2017}
\newcommand{\A}{\mathcal{A}}
\newcommand{\Q}{\mathcal{Q}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\X}{\mathcal{X}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\R}{\mathcal{R}}
\newcommand{\Ls}{{\mathcal{L}_\Sigma}}
\newcommand{\Lc}{{\mathcal{L}}}
\newcommand{\ml}{\mu_{\mathcal{L}}}
\newcommand{\Mn}{M_n(\Ls)}
\newcommand{\Vn}{{M_{n,1}(\Ls)}}
\newcommand{\td}{\tilde{\delta}}
\newcommand{\norm}[1]{\left\lvert#1\right\rvert}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}
\usepackage{exsheets}[2014/09/14] % v0.16 or newer
\SetupExSheets{
  headings = runin ,
  headings-format = \large\bfseries\sffamily ,
  subtitle-format = \large\bfseries\sffamily ,
%  counter-within = section ,
%  counter-format = se.qu\IfQuestionSubtitleT{:} ,
%solution/print = true
}
\newtheorem{defi}{Definition}

\newcommand\myeq{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}}

\newcommand*\fo[1]{\tikz[baseline=(char.base)]{
                \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\usepackage{tikz}
\usetikzlibrary{automata,positioning,trees}

\author{}
%\date{}
\title{TD5 : Langages formels, calculabilité et complexité}

\begin{document}
\pagestyle{fancy}


\section{Context-free grammars}


\begin{question}
  Let us consider the following grammar on the alphabet $\{x,y,+,-,*\}$:
$$ E \rightarrow + EE \mid * EE \mid - EE \mid x \mid y$$

  \begin{enumerate}
    \item Find the leftmost and the rightmost derivations for the
      string $+*-xyxy$.

    \item Show that this grammar in unambiguous.

    \item Find a PDA for this grammar.
  \end{enumerate}
\end{question}


\begin{question}

Using the pumping lemma show that the following languages are not CFG:
\begin{enumerate}
\item $\Lc_0 = \{ a^i b^j c^k \mid i<j<k \}$  
\item $\Lc_1 = \{ a^n b^n c^m \mid n \leq m \leq 2n \}$  
\item $\Lc_2 = \{ a^{2^n} \mid n\in\mathbb{N} \}$  
\item $\Lc_3 = \{ a^{n^2} \mid n\in\mathbb{N} \}$  
\end{enumerate}
\end{question}


\section{Chomsky Normal Form (CNF)}

\begin{defi}
  We recall that a grammar in a CNF when all the production rules are :
  \[
  \begin{array}{lcccr}
    A\rightarrow BC & \mbox{ or } & A\rightarrow a& \mbox{ or } & S\rightarrow \epsilon
  \end{array}
  \]
with $B\neq S$ and $C\neq S$ where $S$ is the start symbol.
\end{defi}

\begin{question}
  Let $G=(\Sigma,N,P,S)$ be a CFG. We suppose that $S$ never appears
  in the right side of a production rule, how can you eliminate all
  the production rules of the form $A\rightarrow \epsilon$ (except
  eventually $S\rightarrow \epsilon$) from $G$ ?
\end{question}

\begin{question}
  Devise a method to transform production rules into CNF form, for the
  following shapes of production rules (we suppose that $S$ does not
  appear):
  \begin{enumerate}
    \item $A\rightarrow bC$
    \item $A\rightarrow Bc$
    \item $A\rightarrow bc$
    \item $A\rightarrow BCD$
    \item $A\rightarrow \alpha_1\alpha_2\alpha_3$ with $\alpha_i\in \Sigma \cup N$
    \item $A\rightarrow \alpha_1\dots\alpha_p$ with $p\geq 3$
    \item $A\rightarrow B$
  \end{enumerate}
\end{question}

\begin{question}
  Devise a  CNF equivalent to the following grammar :

  \[
  \begin{array}{rcrcl}
    S &~~ \rightarrow ~~& CSC & \mid & aB \\
    C & \rightarrow & B & \mid & S \\
    B & \rightarrow & b & \mid & \epsilon \\

  \end{array}
  \]
    
\end{question}


\begin{question}
Devise a polynomial time algorithm (in the size of word and the grammar)
recognizing when a word belongs to a CNF grammar.
\end{question}

\end{document}
