Deviata sada domacich uloh

Vseobecne upozornenie: Ak bola odprednasana vseobecna konstrukcia na riesenie danej ulohy, pouzivajte ju.

Uloha 1

Dokazte, ze trieda bezkontextovych jazykov je uzavreta na operacie

. (zretazenie)
* (iteracia)
U (zjednotenie)

Uloha 2

Dana je bezkontextova gramatika G = (N,T,P,S), kde N = {S,A,B,C}, T = {a,b,c}, s pravidlami

 S -> SS | A | bCC
 A -> epsilon | BC | CB
 B -> aSBA | bASS | ab
 C -> ASA | cB

Zostrojte bezkontextovu gramatiku G' neobsahujucu pravidla tvaru A -> epsilon, taku, ze L(G') = L(G)\{epsilon}.

Uloha 3

Dana je bezkontextova gramatika G = (N,T,P,S), kde N = {S,A,B,C,D,E,F}, T = {a,b,c}, s pravidlami

 S -> BC | aE
 A -> E | Ba | Dc
 B -> SF | EBC | Fcc
 C -> aB | EbE
 D -> DD | SAa | c
 E -> CE | aa
 F -> Ba | SFE | abB

Standardnym postupom zostrojte ekvivalentnu bezkontextovu gramatiku G' taku, ze kazdy jej neterminal sa vyskytuje v (niektorom) odvodeni nejakeho finalneho slova z L(G).

V nasledujucich ulohach su prezentovane modifikacie modelu zasobnikoveho automatu. Zadefinujte takyto modifikovany automat (standardne styri def.) a porovnajte jeho vypoctovu silu so standardnym zasobnikovym automatom (t.j. zistite, ci sa takymito automatmi da akceptovat lubovolny bezkontextovy jazyk a ci existuje jazyk, ktory nie je bezkontextovy, akceptovany takymto automatom). Svoje tvrdenie dokazte.

Uloha 4

Modifikacia zasobnikoveho automatu: automat moze v jednom kroku vypoctu vlozit do zasobnika najviac dva symboly.

Uloha 5

Modifikacia zas. automatu: automat ma dve hlavy na citanie vstupu a jeden zasobnik. Kazda z hlav moze v kazdom kroku bud precitat pismeno zo vstupu alebo ostat na mieste. Hlavy sa pohybuju nezavisle na sebe.

Uloha 6

Modifikacia zas. automatu: automat ma citaciu hlavu sirky 2. To znamena, ze v jednom kroku vypoctu moze citat bud 0, alebo 2 znaky vstupu. Slova neparnej dlzky su doplnene na konci specialnym znakom B nepatriacim do abecedy daneho jazyka.

Uloha 7

Modifikacia zas. automatu: automat, ktory akceptuje vylucne stavom. Slovo je akceptovane, ak na nom existuje vypocet, ktory vedie do akceptacneho stavu, pricom nie je nutne docitat cele slovo.

Uloha 8

Modifikacia zas. automatu: automat, ktory akceptuje stavom a zaroven prazdnou pamatou. Slovo je akceptovane, ak na nom existuje vypocet, ktory vedie do konfiguracie, v ktorej je prazdny zasobnik, precitane cele slovo a automat v akceptacnom stave.

Uloha 9

Lavy kvocient jazykov L₁ a L₂ je jazyk

L = {
      w | existuje slovo u z jazyka L₁ a
         slovo v z jazyka L₂, ze u = wv
    }

Analogicky, pravy kvocient jazykov L₁ a L₂ je jazyk

L = {
      w | existuje slovo u z jazyka L₁ a
         slovo v z jazyka L₂, ze u = vw
    }

Dokazte alebo vyvratte: trieda regularnych jazykov je uzavreta na operaciu laveho (praveho) kvocientu.

Uloha 10

Dokazte, ze trieda bezkontextovych jazykov je uzavreta na homomorfizmus.

Uloha 11

Dokazte, ze nasledujuci tvar je normalnym tvarom bezkontextovej gramatiky (ak L(G) neobsahuje epsilon). Vsetky pravidla su tvaru

 N -> N^* T

kde N su neterminaly, T terminaly.

Uloha 12

V tejto ulohe sa hovori o akceptovani zasobnikovych automatov prazdnou pamatou, resp. koncovym stavom.

Najdite zasobnikovy automat, pre ktory plati

N(A) == L(A)
N(A) != L(A)

!=

Uloha 13

Dokazte, ze trieda bezkontextovych jazykov je uzavreta na prienik s regularnym jazykom (t.j. ak L je bezkontextovy a L' regularny jazyk, potom ich prienik je tiez bezkontextovy).

(Tato uloha sa velmi tazko robi pomocou gramatik :))