Kihagyás

3. gyakorlat

Mai életérzés:

\(S \to aS\)

Előző órai feladat

Ugyanannyi a és b legyen a stringben

S -> \(\varepsilon\) | aSbS | bSaS

HF: +0.5 pont, ezt bizonyítani, hogy helyes megoldás

Nyelvtanok / 6. feladat

Készítsünk nyelvtant az \(\{a, b\}\) betűk feletti nyelvhez, melynek szavai palindrómák

\[ S \to a \mid b \mid aSa \mid bSb \mid \varepsilon \]

\(a, aa, aaaaa, bab, abba, aba, baab, \varepsilon\)

\(\varepsilon: S \Rightarrow \varepsilon\)

\(aaabbaaa: \underline S \Rightarrow a\underline Sa \Rightarrow aa\underline Saa \Rightarrow aaa\underline Saaa \Rightarrow aaab\underline Sbaaa \Rightarrow aaabbaaa\)

Feladat

Nyíl szintax

Levezetésnél ez használatos: \(\Rightarrow\)

Több lépés egyszerre levezetésnél: \(\xRightarrow*\)

Szabályoknál pedig ez: \(\to\)

Szabály

\[\begin{align*} S &\to \varepsilon \mid aSB\\ aB &\to Ba\\ B &\to b \end{align*}\]

Levezetések

\(S \Rightarrow \varepsilon \quad\)

\(S \Rightarrow aSB \Rightarrow aaSBB \Rightarrow aaBB \Rightarrow aaBb \Rightarrow aabb\)

\(S \Rightarrow aSB \Rightarrow aaSBB \Rightarrow aaBB \Rightarrow aBaB \Rightarrow abaB \Rightarrow abab\)

\(S \Rightarrow aSB \Rightarrow aaSBB \Rightarrow aaaSBBB \Rightarrow aaaBBB \Rightarrow aaBaBB \Rightarrow aBaaBB \Rightarrow aBaBaB \Rightarrow abaBaB \Rightarrow ababaB \Rightarrow ababab\)

\(S \Rightarrow aSB \Rightarrow aB \Rightarrow Ba \Rightarrow ba\)

Megállapítás

Elég sus nekem, hogy ez egy "ugyanannyi a, mint b cucc"

Az első szabály adja a \(a^n \, B^n\) nyelvet

\(L = \{u \mid l(u_a) = l(u_b)\}\)

Ez szép és jó, de környezet függő

Nyelvtanok / 7. feladat

Készítsünk nyelvtant a helyes zárójelezés leírására, abc: {(, )}

Szabály - 7.

\[ S \to \varepsilon \mid S(S)S \]

HF: A felső szabály formális bizonyításáért jár +0.5 pont

\[ S \to \varepsilon \mid () \mid (S) \mid S() \mid ()S \mid S()S \mid S(S) \mid (S)S \mid S(S)S \]

Példák

\(\varepsilon, (), (()), ()(), (()())\)

Levezetések - 7.

\(S \Rightarrow \varepsilon\)

\(S \Rightarrow \underline S(\underline S)\underline S \xRightarrow* ()\)

\(S \Rightarrow \underline S(S)\underline S \xRightarrow* (\underline S) \Rightarrow (\underline S(\underline S)S)\xRightarrow* (()S) \Rightarrow (()\underline S(S)\underline S) \xRightarrow* (()(\underline S)) \Rightarrow (()(\underline S(\underline S)\underline S)) \xRightarrow* (()(()))\)

Környezetfüggetlen nyelvtanok

Környezetfüggetlen nyelvtanok / 1. feladat

Írjon fel környezetfüggetlen nyelvtant az alábbi alakú listák szintaxisának leírására:

[alma, körte, szilva]

A nyelvtan terminális szimbólumai legyenek a következők:

  • n (nyitó szögletes)
  • e (lista eleme)
  • v (vessző)
  • c (csukó szögletes)

A fenti példa tehát a nevevec szónak felel meg. További helyes szavak: nc, nec, nevec stb.

Rajzolja fel a fenti példa szintaxisfáját, és adja meg a szó levezetését!

Nyelvtan

\[\begin{align*} S &\to nc \mid neA \\ A &\to veA \mid c \\ \end{align*}\]
\[ \lor \]
\[\begin{align*} S &\to nLc \mid nc \\ L &\to evL \mid e \\ \end{align*}\]

Szintaxis fa

asd

\[ \begin{array}{} S \\ \swarrow \downarrow \searrow \\ n \enspace e \enspace A \\ \qquad \swarrow \downarrow \searrow \\ \qquad v \enspace e \enspace A \\ \qquad\qquad\qquad\searrow \\ \qquad\qquad\qquad\qquad c \end{array}\]

Környezetfüggetlen nyelvtanok / 2. feladat

Írjon fel környezetfüggetlen nyelvtant C stílusú deklarációsorozatok szintaxisának leírására:

char betuje( string s, int index );

int osszeg( int x, int y );

Terminális szimbólumok:

  • a (azonosító: típusok és paraméterek nevei)
  • n (nyitó zárójel)
  • c (csukó zárójel)
  • v (vessző)
  • p (pontosvessző)

A fenti példa az aanaavaacpaanaavaacp szónak felel meg.

További helyes szavak: \(\varepsilon\), aancp, aanaacp, aancpaancp stb.

Nyelvtan - 2.

\[\begin{align*} S &\to \varepsilon \mid aanA \\ A &\to aacp\red{S} \mid cp\red{S} \mid aavA \end{align*}\]
\[ \begin{align*} S &\to \varepsilon \mid DS \\ D &\to aanLcp \mid aancp \\ L &\to aa \mid aavL \\ \end{align*} \]
\[ \begin{align*} S &\to \varepsilon \mid DS \\ D &\to aanLcp \\ L &\to \varepsilon \mid aa \mid aavF \\ F &\to aa \mid aavF \\ \end{align*} \]
  1. órán ZH lesz (március 19. afaik)