Formális nyelvek 16. csoport, 1. gyakorlati zárthelyi, 2011. március 16.

A maximálisan megszerezhető pontszám 15, melyből legalább 5 pontot kell megszerezni a sikeres teljesítéséhez.

1. Az EP programozási nyelvben az azonosítók az angol ábécé kis és nagybetűit, decimális jegyeket és _ jelet tartalmazhatnak a következő szabályok szerint:

a. Minden azonosító nagybetűvel kezdődik.

b. Az _ jelet mindig követnie kell egy nagybetűnek.

Írja le ezt az azonosító fogalmat BNF, EBNF és szintaxis-gráfok segítségével!

(1-1 pont, összesen 3).

2. A klózokat a következő BNF leírás segítségével definiáljuk:

<klóz>::= <elem>| <elem>V<klóz>

<elem>::= A|B|C|┐A |┐B|┐C

Helyes klózok-e a leírás szerint az alábbiak?

a. ┐A V B V ┐C

b. A V ┐┐B V C

(1-1 pont, összesen 2)

3. A teknőc grafikában F jelöli azt, hogy a toll az irányának megfelelően húz egy egységnyi vonalat, + jelöli, hogy a toll balra fordul 90 fokkal, míg – azt, hogy jobbra fordul 90 fokkal.

Legyen u Î {F,+,-}* tetszőleges rajz.

a. Mikor igaz, hogy u végrehajtása után a toll ellenkező irányba mutat, mint kezdetben?

(1 pont)

b. Mikor igaz, hogy u végrehajtása után a toll ugyanabban a pontban lesz és a toll ugyanabba az irányba mutat, mint kezdetben? (3 pont)

(Összesen 4 pont)

4. L1, L2, L3, S, T valamely legalább két betűs ábécé feletti nyelvek. Igazak-e az alábbi összefüggések (ha valamelyik irány nem teljesül, mutasson ellenpéldát)?

a. (T*S*)* = (S*T*)* (1 pont)

b. (L1∩L2)L3 = L1L3∩ L2L3 (2 pont)

(Összesen 3 pont)

5. Készítsen lehető legmagasabb típusú nyelvtant az alábbi nyelvhez!

L= {u; u Î {a,b,c}* és u-ban az a betűk száma páros, biztosan a-ra végződik és nem tartalmaz két egymás utáni b betűt, illetve két egymás utáni c betűt} (3 pont)