Egzamin poprawkowy 2009/2020

k

I

Imię i nazwisko: Nr indeksu: ____

w

1. Uszereguj języki opisane przez podane wzorce od najmniejszego do największego (w sensie zawierania zbiorów).

-um

-H [Z] *( [El

■hej

4 I (El

4*![V]

m m

*\ IEI ai m 4 m

fctfDg]

| [El

-/im

4 I *1 [El

Csy następująca gramatyka jest jednoznaczna? iS* - * nSa | bSb \ e Czy w następującej    gramatyce

można wyprowadzić    puste słowo?

S —* SaX | Xb_t X —» ab | e Czy w następującej    gramatyce

można    wyprowadzić    słowo abab?

S —* aSa | bSb | e

Czy język generowany przez następującą gramatykę jest    skończony?

5 — XXX, X -> a | b Czy następująca gramatyka generuje pusty język? S —* abS \ SbS | a

Dopełnienie każdego języka bezkontek-stowego jest językiem bezkontekstowym. Sklejenie języków regularnych jest językiem regularnym.

Każdy język częściowo obliczalny jest obliczalny.

Gramatyki ogólne (typu 0) opisują języki częściowo obliczalne.

Gramatyki liniowe opisują języki regularne.

Automat stosowy musi być deterministyczny.

Lewostronna faktoryzacja powoduje, że gramatyka bezkontekstowa staje się jednoznaczna.

Eliminacja e-przejść w automacie skończonym może spowodować wykładniczą eksplozję liczby jego stanów.

Leksem jest reprezentowany przez parę: żeton, atrybut.

Analizator leksykalny stara się, przede wszystkim, rozpoznać leksem pasujący do jak najwcześniejszej reguły w specyfikami.

Parsery [S]LR(1) odtwarzają drzewo wyprowadzenia od korzenia do liści. Analizator leksykalny generowany przez [FjLexa to rodzaj niedeterministycznego automatu stosowego.

Parsery LL(1) obchodzą drzewo wyprowadzenia w porządku prefiksowym.

Yacc i Bison implementują mechanizm atrybutów syntezowanych.

Konstrukcja parsera LL(1) nie może się udać dla gramatyki niejednoznacznej.

l)fc1

/zorcóv

4?

2. Dopasuj automaty skończone do wzorców opisujących akceptowane przez nie języki.

a)

Hi

i

a,b

M t

-Ł | b I b* ab* ab*

-f- I Cl (oo)*o ■fi B I (“ I 6(aa)*a6)*

•f [SI

6⁺

| I dl (<K* | 66)*

4| ta

41 m qu 4i m

2010/02/17 14:42