Pytania i odpowiedzi (1 / 2)
AUG pytania T/N
1.
czy następująca gramatyka jest jednoznaczna? S → aS | Sb | e
NIE
2.
czy następująca gramatyka jest jednoznaczna? S → aSb | bSa | e
TAK
3.
czy następująca gramatyka jest jednoznaczna? S → aSb | bSa |
TAK
4.
czy następująca gramatyka jest jednoznaczna? S → SS | Sb | e
NIE
5.
czy w następujacej gramatyce można wyprowadzić puste słowo? S→ XXX, X → ab | ba | e
TAK
6.
czy w następujacej gramatyce można wyprowadzić puste słowo? S→ aSb | X, X → bSa | e
TAK
7.
czy w następujacej gramatyce można wyprowadzić puste słowo? S→ aSa | bSb | ba
NIE
8.
czy w następujacej gramatyce można wyprowadzić słowo puste? S→ abS | Sba | aa
NIE
9.
czy w następujacej gramatyce można wyprowadzić słowo „abaa”? S→ abS | Saa | e
TAK
10.
czy w następujacej gramatyce można wyprowadzić słowo „abab”? S→ SabS | e
TAK
11.
czy w następujacej gramatyce można wyprowadzić słowo „abab”? S→ aSa | bSb | ab
NIE
12.
czy w następujacej gramatyce można wyprowadzić słowo „baba”? S→ aSb | bSa | e (
TAK
13.
czy język gramatyki jest skończony? S→ abS | bSa | a
NIE
14.
czy język generowany przez następującą gramatyke jest skończony? S→ aSb | bSa | e
NIE
15.
czy język generowany przez następującą gramatyke jest skończony? S→ SS | bSb | ab
NIE
16.
czy następująca gramatyka generuje pusty język? S→ SS | SbS | aSb
TAK
17.
czy następująca gramatyka generuje pusty język? S→ aSb | bSa | SS
TAK
18.
czy następująca gramatyka generuje pusty język? S→ SaS | bSb | a
NIE
19.
czy następująca gramatyka generuje pusty język? S→ SS | bSb | a
NIE
20.
automat stosowy w każdym kroku wczytuje dokładnie jeden znak?
NIE
21.
tablica konstruowana w algorytmie CYK zawiera liczby całkowite?
NIE
22.
Analizator leksykalny generowany przez Flexa to rodzaj automatu skończonego?
TAK
23.
Analizator leksykalny generowany przez Flexa to rodzaj maszyny Turinga?
NIE
24.
Analizator składniowy generowany przez Yacca/Bisona to rodzaj wielotaśmowej maszyny Turinga?
NIE
25.
Analizator składniowy generowany przez Yacca/Bisona to rodzaj automatu stosowego?
TAK
26.
Determinizacja automatu skończonego może spowodować wykładniczą eksplozję liczby stanów?
TAK
27.
Dla każdego języka regularnego istnieje rozpoznający go automat skończony?
TAK
28.
Eliminacja e-przejść w automacie skończonym może spowodować kwadratowy wzrost liczby krawędzi?
TAK
29.
Gramatyki liniowe opisują języki regularne?
TAK
30.
Jeśli języki A i Ā są częściowo obliczalne, to są obliczalne?
TAK
31.
Jeśli język A jest obliczalny to Ā też jest obliczalny?
TAK
32.
Jeśli gramatyka jest jednoznaczna to każde słowo, które można z niej wyprowadzić ma tylko jedno drzewo wyprowadzeń?
TAK
33.
Jeśli gramatyka jest jednoznaczna to każde słowo, które mozna z niej wyprowadzić ma tylko jedno wyprowadzenie?
NIE
34.
Język STOP jest obliczalny?
NIE
35.
Język STOP jest częściowo obliczalny?
NIE
36.
Każdy język skończony jest regularny?
TAK
37.
Każdy język kontekstowy jest obliczalny?
TAK
38.
Każdy język obliczalny jest kontekstowy?
NIE
39.
Każdy język regularny jest bezkontekstowy?
TAK
40.
Każdy język regularny jest skończony?
NIE
41.
Każdy język bezkontekstowy jest skończony?
NIE
42.
Każdy język bezkontekstowy jest kontekstowy?
TAK
43.
Obliczenie automatu stosowego może być nieskończone („zapętlać się”)?
TAK
44.
Obliczenie automatu stosowego ma zawsze dokładnie tyle kroków, ile znaków ma wczytane słowo?
NIE
45.
Przecięcie języków bezkontekstowych jest językiem bezkontekstowym?
NIE
46.
Przecięcie języków regularnych jest językiem regularnym?
TAK
47.
Suma języków regularnych jest językiem regularnym?
TAK
48.
Suma języków bezkontekstowych jest bezkontekstowa?
TAK
49.
Sklejanie języków bezkontekstowych jest językiem bezkontekstowym?
TAK
50.
Sklejanie języków regularnych jest językiem regularnym?
TAK