%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Welcome to Overleaf --- just edit your LaTeX on the left,
% and we'll compile it for you on the right. If you open the
% 'Share' menu, you can invite other users to edit at the same
% time. See www.overleaf.com/learn for more info. Enjoy!
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[12pt]{article}
%\usepackage[english]{babel}
\usepackage[magyar]{babel}
\usepackage[utf8x]{inputenc}
\usepackage{amsmath}
\usepackage{tikz}
\usetikzlibrary{arrows,automata}

\title{Formális nyelvek és fordítóprogramok \protect\\ 1. labor}

\date{}

\begin{document}
\maketitle

\textbf{Alapfogalmak:}

- \textit{ábécé}: véges szimbólumok halmaza

- nyelvek megadása történhet: elemeik felsorolásával, tulajdonságuk megadása segítségével vagy nyelvtannal.
  
- generatív nyelvtan a \(G = (N, T, P, S)\) rendezett négyes, ahol:
\begin{itemize}
\itemsep0em 
\item \(N\), a változók (nemterminális jelek),
\item \(T\), a terminális jelek ábécéje, ahol \(N ∩ T = ∅\),
\item  \(P\) a helyettesítési szabályok,
\item  \(S \in N\) a nyelvtan kezdőszimbóluma.
\end{itemize}

\noindent\rule{4cm}{0.4pt}

\textbf{1.1} Adjunk meg egy nyelvtant, amely az \(L = \{uu^{-1}| u \in \{a,b\}^*\}\) nyelvet generálja, és határozzuk meg a típusát.
\newline

% Környezetfüggetlen kiterjesztett nyelv:
% S \rightarrow  \epsilon | aSa | bSb

% Környezetfüggetlen nyelvtanként:
% S' \rightarrow  \epsilon | S
% S \rightarrow   aSa | aa
% S \rightarrow   bSb | bb

% G = ({S, S'}, {a, b}, P, S')

\textbf{1.2}   Adjunk meg a következő nyelvtan által generált nyelvet: \newline
\(G = (N, T, P, S)\), ahol \(N = \{S, A, B\}, T = \{a,*,+,(,)\}\) és \(P\) elemei: \newline
S \rightarrow   S + A | A \newline
A \rightarrow   A * B | B \newline
B \rightarrow (S) | a \newline

% Helyesen zárójelezett aritmetikai kifejezések.

\textbf{1.3}   Adjunk meg egy nyelvtant, amely a természetes számokat generálja.
\newline
% S \rightarrow AS | A
% A \rightarrow 0|1|2...|9

\textbf{1.4}   Adjunk meg egy-egy nyelvtant a következő nyelvek generálására:
\(L_1 = \{a^{n}b^mc^p| n \geq 1, m \geq 1, p \geq 1\}\) \newline
\(L_2 = \{a^{n}b^n| n \geq 1\}\) \newline
\(L_3 = \{a^{n}b^m | n \geq 1, m \geq 1\}\) \newline
\(L_4 = \{a^{n}b^m | n \geq 0, m \geq 1\}\) \newline
\(L_5 = \{a^{n}b^m | n \geq 1, m \geq 0\}\) \newline
\(L_6 = \{a^{n}b^m | n \geq 0, m \geq 0\}\) \newline
\(L_7 = \{a^{n}b^m| n \geq m \geq 1\}\) \newline

\textbf{1.5} Az \(L_3 = \{a^{n}b^m | n \geq 1, m \geq 1\}\) nyelvtant a következő véges automatával reprezentálhatjuk. Írjunk programot amely eldönti, hogy egy adott szó eleme a nyelvnek

\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3.5cm,
        scale = 1,transform shape]

  \node[state,initial] (q0) {$q0$};
  \node[state] (q1) [right of=q0] {$q1$};
  \node[state,accepting] (q2) [right of=q1] {$q2$};

    \path[->] 
    (q0) edge  node {a} (q1)
    (q1) edge  node  {b} (q2)
          edge [loop above] node {a} ()
    (q2) 
          edge [loop above] node {b} ();

%   \path (q0) edge              node {$a$} (q1)
%         (q1) edge              node {$a$} (q1)
%         (q1) edge              node {$b$} (q2)
%         (q2) edge              node {$b$} (q2);

\end{tikzpicture}
\end{center}

%  L1: S \rightarrow ABC, A \rightarrow aA | a, B \rightarrow bB | b, C \rightarrow cC | c
%  L2: S \rightarrow aSb | ab
%  L3: S \rightarrow AB, A \rightarrow aA | a, B \rightarrow bB | b
%  L4: S \rightarrow AB | B, A \rightarrow aA | a, B \rightarrow bB | b
%  L5: S \rightarrow AB | A, A \rightarrow aA | a, B \rightarrow bB | b
%  L6: S \rightarrow AB | A | B | epsilon, A \rightarrow aA | a, B \rightarrow bB | b
%  L7: S \rightarrow aSb | ab | aS 

\clearpage

\textbf{Megoldott feladatok:}

\textbf{1.4} Adjunk meg egy-egy nyelvtant a következő nyelvek generálására:

a) \(L_1 = \{a^{2n-1} | n \geq 1\}\) 

Az automata olyan nyelvet ismer fel, amely páratlan számú \(a\)-t tartalmaz.
Legyen a kezdőállapot S. Ez esetben meg kell adjunk egy vagy több olyan szabályt, amely generálja a nyelv szavait. 

\(S \rightarrow aaS\)  szabállyal mindig biztosítunk páros számú a jelenlétét. 

\(S \rightarrow a\)  szabály pedig lezárást biztosít. Amennyiben \(n=1\), ezt a szabályt alkalmazzuk, illetve amennyiben \(n>1\), az előző szabályt alkalmazzuk amíg \(2n-2\)-nyi \(a\) nem lesz, utolsó helyettesítésként pedig a második szabály garantálja, hogy páratlan számú \(a\)-val fejezzük be a helyettesítést. 

Kompaktabb jelöléssel a szabályrendszer a következő: \(S \rightarrow aaS | a\) 

 \textit{Miért nem lenne jó az \(S \rightarrow aS | a\) nyelvtan?}\newline
Valóban felismerné a páratlan számú a-t tartalmazó szavakat, de az automata felismerne minden olyan szót, amely \(a\)-kat tartalmaz, nem csak a páratlan számúakat.\newline 

\newline 

b) \(L_2 = \{a^{2n} | n \geq 1\}\) 

A fenti példához hasonlóan, az \(S \rightarrow aaS | aa\)  szabályrendszert keressük.


\end{document}