wayground logo

Free Printable Worksheets

NEW

Font size

S
M
L
XL
Worksheets

Automaty

Total questions: 64

Worksheet time: 42mins

Name
Class
Date
1.

Podany poniżej diagram przejść przedstawia

a)

automat DAS

b)

automat NAS nie będący DAS

c)

automat ε-NAS nie będący NAS

d)

automat ze stosem AZS

2.

Język rozpoznawany przez automat DAS przedstawiony na powyższym diagramie przejść, to zbiór wszystkich słów nad alfabetem Σ = {0,1}

a)

zawierających parzystą liczbę symobli 1

b)

zawierających nieparzystą liczbę symboli 0

c)

zawierających nieparzystą liczbę symboli 0 i parzystą liczbę symboli 1

d)

o nieparzystej długości

3.

Dany jest automat ε - NAS (Q, Σ, ð, q0, F). Prawdą jest, że

a)

nie można przekształcić go na równoważny automat NAS

b)

równoważny mu automat NAS będzie miał |Q| stanów

c)

równoważny mu automat NAS będzie miał |2^q| stanów

d)

równoważny mu automat NAS będzie miał |QxΣ| stanów

4.

Przy konwersji automatu Mealy'ego na automat Moore'a

a)

nie zmienia się zbiór stanów

b)

nie zmienia się funkcja przejścia

c)

nie zmienia się funkcja wyjścia

d)

nie zmienia się alfabet wyjściowy

5.

Jeżeli automat ε-NAS znajduje się w jednym stanie q i czyta symbol wejściowy a oraz wartość funkcji przejścia ð(q,a) = {q} gdzie q jest stanem akceptującym, to automat ten

a)

zakończony obliczanie i odrzuci słowo wejściowe

b)

zakończony obliczanie i zaakceptuje słowo wejściowe

c)

będzie kontynuować obliczanie

d)

będzie kontynuować obliczanie tylko wtedy, gdy istnieje możliwość wykonania jednego lub kilku ε-przejść ze stanu q, w wyniku których automat może dotrzeć do stanu posiadającego przejście dla symbolu a

6.

Język rozpoznawany przez powyższy automat NAS, to zbiór wszystkich słów nad alfabetem Σ = {a,b}

a)

opisanych wyrażeniem regularnym b*aa

b)

zawierających podsłowo aa

c)

rozpoczynających się podsłowem aa

d)

kończących się podsłowem aa

7.

W przedstawionym powyżej automacie

ε-NAS, ε-domknięciem stanu q2 jest zbiór

a)

{q1}

b)

{q0,q1}

c)

{q1,q2}

d)

{q0,q1,q2}

8.

Po konwersji automatu ε-NAS z zadania 7 w automat NAS zbiór stanów akceptujących będzie równy

a)

{q1}

b)

{q0,q1}

c)

{q0,q1,q2}

d)

{q1,q2}

9.

Które z podanych niżej zapisów jest prawem algebry wyrażeń regularnych

(r, s, t są dowolnymi wyrażeniami regularnymi)

a)

rs = sr

b)

rε = ε

c)

r∅ = ∅

d)

r r* = r*

10.

Wyrażenie regularne (0|1)*1 opisuje zbiór wszystkich słów nad alfabetem Σ = {0,1}

a)

zawierających przynajmniej jeden symbol 1

b)

parzystej długości kończących się symbolem 1

c)

nieparzystej długości kończących się symbolem 1

d)

kończących się symbolem 1

11.

W wyrażeniu regularnym a(a*|b)

a)

najpierw wykonywane jest domknięcie *, potem suma |, a na końcu założenie

b)

najpierw wykonywana jest suma, potem domknięcie, a na końcu założenie

c)

najpierw wykonywane jest założenie, potem domknięcie, a na końcu suma

d)

kolejność operacji jest inna od każdej z wyżej podanych

12.

jest językiem:

a)

regularnym

b)

bezkontekstowym, ale nie jest on regularny

c)

kontekstowym, ale nie jest on bezkontekstowy

d)

rekurencyjnie przeliczalnym, ale nie jest on kontekstowy

13.

Dana jest następująca gramatyka G = ({S, A, B}, {a, b, c}, P, S), gdzie:

P:

S → ABac

A → cA|ac

B → AbB

Gramatyka jest:

a)

regularna

b)

bezkontekstowa, ale nie jest regularna

c)

kontekstowa, ale nie jest bezkontekstowa

d)

jest gramatyką ogólnego rodzaju, która nie jest gramatyką kontekstową

14.

Który z poniższych sposobów zapisu nie służy do opisu gramatyk bezkontekstowych

a)

diagram przejść

b)

notacja Backusa-Naura

c)

rozszerzona notacja Backusa-Naura

d)

wykresy składniowe

15.

Wybierz zdanie prawdziwe z niżej podanych

a)

Każdy język bezkontekstowy jest językiem regularnym

b)

Każdy język kontekstowy jest językiem rekurencyjnie przeliczalnym

c)

Każdy język rekurencyjnie przeliczalnym jest językiem rekurencyjnym

d)

Każdy język rekurencyjnie przeliczalnym jest językiem kontekstowym

16.

Przedstawiony powyżej wykres składniowy odpowiada następującej produkcji (produkcjom) w zapisie symbolicznym)

a)

C → 1A|B

b)

C → AB|1

c)

C → 1AB

d)

C → AB1

17.

Jeśli język jest rozpoznawany przez pewną maszynę Turinga z własnością stopu, to jest on

a)

regularny

b)

bezkontekstowy

c)

rekurencyjny

d)

rekurencyjnie przeliczalny, ale nie musi być rekurencyjny

18.

Maszyna Turinga

a)

może przesuwać głowicę nad taśmą tylko w prawo

b)

może przesuwać głowicę nad taśmą zarówno w lewo jak i w prawo

c)

może czytać symbole z taśmy, ale nie może nic zapisywać na taśmie

d)

może zapisywać symbole na taśmie, ale nie może odczytywać symboli z taśmy

19.

Który z podanych problemów jest rozstrzygalny

a)

problem stopu dla NAS

b)

problem stopu dla maszyny Turinga

c)

problem akceptacji dla maszyny Turinga

d)

problem określenia czy język rozpoznawany przez maszynę Turinga jest regularny

20.

Jeśli maszyna Turinga M kończy obliczanie dla pewnego słowa w odrzuceniem, to

a)

słowo 'w' nie należy do języka L(M) rozpoznawanego przez tę maszynę

b)

słowo 'w' należy do języka L(M) rozpoznawanego przez tę maszynę

c)

jest to maszyna z własnością stopu

d)

długość słowa 'w' jest większa od liczby stanów tej maszyny

21.

Podany powyżej diagram przejść przedstawia

a)

automat DAS

b)

automat NAS nie będący DAS

c)

automat ε-NAS nie będący NAS

d)

automat ze stosem AZS

22.

Język rozpoznawany przez automat przedstawiony na poniższym diagramie przejść, to zbiór wszystkich słów nad alfabetem Σ = {0,1}

a)

o długości 1

b)

o długości co najmniej 1

c)

o nieparzystej długości

d)

o nieparzystej długości złożonych z samych zer lub z samych jedynek

23.

Przy konwersji automatu Moore'a na automat Melay'ego

a)

zmienia się zbiór stanów

b)

zmienia się funkcja przejścia

c)

zmienia się funkcja wyjścia

d)

zmienia się alfabet wejściowy

24.

Jeżeli automat ε-NAS znajduje się w jednym stanie q i czyta symbol wejściowy 'a' oraz wartość funkcji przejścia ð(q,a) = ∅, to automat ten

a)

zakończy obliczenie i zaakceptuje słowo wejściowe

b)

zakończy obliczenie i odrzuci słowo wejśćiowe

c)

zawsze będzie kontynuować obliczenie

d)

będzie kontynuować obliczenie tylko wtedy, gdy istnieje możliwość wykonania jednego lub kilku ε-przejść ze stanu q, w wyniku których automat może dotrzeć do stanu posiadającego przejście dla symbolu 'a'

25.

W wyrażeniu regularnym (a(a|b))*

a)

najpierw wykonywane jest domknięcie *, potem suma |, a na końcu złożenie

b)

najpierw wykonywana jest suma, potem złożenie a na końcu domknięcie

c)

najpierw wykonywana jest suma, potem domknięcie, a na końcu złożenie

d)

kolejność operacji jest inna od każdej z wyżej podanych

26.

Wybierz zdanie fałszywe z niżej podanych

a)

Każdy język bezkontekstowy jest językiem kontekstowym

b)

Każdy język bezkontekstowy jest językiem regularnym

c)

Każdy język rekurencyjny jest językiem rekurencyjnie przeliczalnym

d)

Każdy język kontekstowy jest językiem rekurencyjnie przeliczalnym

27.

Przedstawiony powyżej wykres składniowy odpowiada następującej produkcji (produkcjom) w zapisie symbolicznym

a)

A → C|0B

b)

A → B0|C

c)

A → 0CB

d)

A → 0|B|C

28.

Maszyna Turinga

a)

ma ograniczoną taśmę, z które może tylko czytać symbole z alfabetu taśmowego

b)

ma ograniczoną taśmę, z które może czytać i na każdą może zapisywać symbole z alfabetu taśmowego

c)

ma nieograniczoną taśmę, z której może czytać i na którą może zapisywać symbole z alfabetu taśmowego

d)

ma nieograniczoną taśmę, z której może tylko czytać symbole z alfabetu taśmowego

29.

Zbiór wszystkich języków nad danym alfabetem jest

a)

skońćzony

b)

nieskończony ale przeliczalny

c)

nieprzeliczalny

d)

nie można stwierdzić która z poprzednich odpowiedzi jest poprawna bez znajomości alfabetu

30.

Dany jest automat NAS(Q,Σ,ð,q0,F), gdzie zbiór stanów jest n-elementowy.

Prawdą jest, że

a)

każdy równoważny mu automat DAS będzie miał dokładnie 2^n stanów

b)

otrzymany w wyniku konwersji automat DAS ma 2^n stanów, przy czym zwykle część jego stanów stanowi stany nieosiągalne ze stanów początkowego i takie stany można usunąć

c)

równoważny mu automat DAS będzie miał n stanów

d)

nie można przekształcić go na równoważny automat DAS

31.

Język L (a^n b^m: n,m ∈ N) jest językiem

a)

regularnym

b)

bezkontekstowym, ale nie jest on regularny

c)

kontekstowym, ale nie jest on bezkontekstowy

d)

rekurencyjnie przeliczalnym, ale nie jest on kontekstowy

32.

Podany powyżej diagram przejść przedstawia

a)

automat DAS

b)

automat ze stosem AZS

c)

automat NAS nie będący DAS

d)

automat ε-NAS nie będący NAS

33.

Język rozpoznawany przez automat przedstawiony na powyższym diagramie przejeść, to zbiór wszystkich słów nad alfabetem Σ = {0,1}

a)

kończących się symbolem 1

b)

zawierających przynajmniej jeden symbol 0

c)

zawierających przynajmniej jeden symbol 0 i kończących się symbolem 1

d)

żaden z powyższych

34.

Automat Mealy'ego w odpowiedzi na słowo wejściowe o długości n generuje

a)

słowo wyjściowe o długości n

b)

słowo wyjściowe o długości n+1

c)

słowo wyjściowe o długości n-1

d)

słowo wyjściowe o długości innej od wyżej podanych

35.

W przedstawionym powyżej automacie ε-domknięciem stanu q1, jest

a)

{q1}

b)

{q1,q2}

c)

{q1,q2,q3}

d)

{q2}

36.

Po konwersji automatu ε-NAS z zadania 7 w automat NAS zbiór stanów akceptujących będzie równy

a)

{q2}

b)

{q2,q3}

c)

{q1,q2}

d)

{q1,q2,q3}

37.

Zbiór języków nad danym alfabetem rozpoznawalnych przez maszyny Turinga jest

a)

skończony

b)

nieskończony, ale przeliczalny

c)

nieprzeliczalny

d)

nieskończony, ale nie można określić czy jest przeliczalny

38.

Który z podanych problemów jest nierozstrzygalny

a)

problem stopu dla DAS

b)

problem akceptujący dla DAS

c)

problem stopu dla NAS

d)

problem akceptacji dla maszyny Turinga

39.

Język rozpoznawany przez poniższy automat NAS, to zbiór wszystkich słów nad alfabetem Σ = {a,b}

a)

zawierających podsłowo aa

b)

kończących się podsłowem aa

c)

rozpoczynających się podsłowem aa

d)

rozpoczynającym się dowolną liczbą (w tym zero) symboli b, po których następują dokładnie dwa symbole a

40.

Które z podanych niżej zapisów nie jest prawem algebry wyrażeń regularnych (r,s,t są dowolnym wyrażeniami regularnymi)

a)

r(s|t) = rs|rt

b)

r∈ = r

c)

r|∅ = r

d)

rs = sr

41.

Wyrażenie regularne 1(0|1)*|0 opisuje zbiór wszystkich słów nad alfabetem Σ = {0,1}

a)

rozpoczynających się symbolem 1 i kończących symbolem 0

b)

kończących się symbolem 1

c)

rozpoczynających się symbolem 1

d)

rozpoczynających się symbolem 1 oraz słowo złożone z pojedynczego symbolu 0

42.

Dana jest następująca gramatyka G = ({S, A, B}, {a, b, c}, P, S), gdzie:

P:

S → cB

A → bB|C

B → aA

Gramatyka jest:

a)

regularna

b)

bezkontekstowa, ale nie jest regularna

c)

kontekstowa, ale nie jest bezkontekstowa

d)

jest gramatyką ogólnego rodzaju, która nie jest gramatyką kontekstową

43.

Język rozpoznawany przez podany poniżej automat NAS to zbiór wszystkich słów nad alfabetem Σ = {a,b}

a)

zawierających podsłowo bb

b)

kończących się podsłowem bb

c)

rozpoczynających się podsłowem bb

d)

zawierających przynajmniej 2 symbole b

44.

Wyrażenie regularne ((0|1)(0|1))*1 opisuje zbiór wszystkich słów

a)

nieparzystej długości kończących się symbolem 1

b)

parzystej długości kończących się symbolem 1

c)

kończących się symbolem 1

d)

rozpoczynających się i kończących symbolem 1

45.

W wyrażeniu regularnym 0(0|1*)

a)

najpierw wykonane jest domkniecie *, potem suma |, a na końcu złożenie

b)

najpierw wykonana jest suma, potem domknięcie, a na końcu złożenie

c)

najpierw wykonywane jest złożenie, potem suma, a na końcu domknięcie

d)

kolejność operacji jest inna od każdej z podanych

46.

Jeśli dwa automaty DAS rozpoznają ten sam język, to

a)

automaty minimalne dla każdego z nich są zawsze takie same

b)

mogą istnieć różne automaty minimalne dla każdego z tych automatów

c)

nie dla każdego z nich musi istnieć automat minimalny

d)

automaty te są identyczne z dokładnością do nazwy stanów

47.

Wybierz zdanie fałszywe z niżej podanych

a)

W gramatyce jednoznacznej każde słowo ma tylko jedno drzewo wywodu

b)

W gramatyce jednoznacznej każde słowo ma tylko jedno wyprowadzenie

c)

W gramatyce jednoznacznej każde słowo ma jedno wyprowadzenie prawostronne i jedno wyprowadzenie lewostronne

d)

W gramatyce niejednoznacznej istnieje słowo, które ma dwa różne drzewa wywodu.

48.

Wybierz zdanie prawdziwe z niżej podanych

a)

W automatach AZS jest dokładnie jedno przejście z każdego stanu dla danego symbolu wejściowego

b)

Wartość funkcji przejścia automatu AZS zależy tylko od stanu i symbolu wejściowego

c)

Wartość funkcji przejścia automatu AZS zależy tylko od stanu i symbolu na szczycie stosu

d)

W etykiecie a,b -> c, opisującej przejście automatu AZS na diagramie przejść, każdy ze znaków a, b, c może być słowem pustym

49.

Przedstawiony powyżej wykres składniowy odpowiada następującej produkcji (produkcjom) w zapisie symbolicznym

a)

A → A1|A21

b)

A → A1|A2

c)

A → A1A2|1

d)

A → A11|A21

50.

Spośród DAS, NAS, AZS, maszyn Turinga najszerszą klasę języków formalnych rozpoznają

a)

deterministyczne automaty skończone DAS

b)

niedeterministyczne automaty skończone NAS

c)

automaty ze stosem AZS

d)

maszyny Turinga

51.

Język rozpoznawany przez automat przedstawiony na powyższym diagramie przejść, to zbiór wszystkich słów nad alfabetem Σ = {0,1}

a)

rozpoczynających się i kończących symbolem 0

b)

kończących się symbolem 0

c)

rozpoczynających się symbolem 0 i zawierających przynajmniej 2 symbole 0

d)

o długości co najmniej 2 rozpoczynających się i kończących symbolem 0

52.

Konwersja, w której nie zmienia się funkcja przejścia to:

a)

NAS z ∈-ruchami w NAS

b)

NAS w DAS

c)

Mealy'ego w Moore'a

d)

Żadna z powyższych

53.

Język rozpoznawany przez podany powyżej automat NAS to zbiór wszystkich słów nad alfabetem Σ = {a,b}

a)

rozpoczynających się symbolem b

b)

rozpoczynających się symbolem b, po którym może wystąpić dowolna liczba symboli a

c)

o długości co najmniej 1

d)

zawierających dokładnie 1 symbol b

54.

W przedstawionym poniżej automacie ∈-domknięciem stanu q1 jest

a)

{q1}

b)

{q0,q1}

c)

{q0,q1,q2}

d)

∅

55.

Po konwersji automatu ∈-NAS z zadania 7 w automat NAS, zbiór stanów akceptujących będzie równy

a)

{q2}

b)

{q0,q2}

c)

{q1,q2}

d)

{q0,q1,q2}

56.

Które z podanych niżej zapisów nie jest prawem algebry wyrażeń regularnych (r, s, t są dowolnymi wyrażeniami regularnymi)

a)

(r *)* = r *

b)

r∈ = r

c)

r|∅ = ∅

d)

r(s|t) = rs|rt

57.

Wyrażenie regularne 0(0|1*)11 opisuje zbiór wszystkich słów nad alfabetem Σ = {0,1}

a)

kończących się podsłowem 11

b)

rozpoczynających się symbolem 0

c)

rozpoczynających się symbolem 0 i kończących się podsłowem 11

d)

o długości co najmniej 4 rozpoczynających się symbolem 0 i kończących się podsłowem 11

58.

W wyrażeniu regularnym 0(0|1)*

a)

najpierw wykonywane jest domknięcie *, potem suma |, a na końcu złożenie

b)

najpierw wykonywana jest suma, potem domknięcie, a na końcu złożenie

c)

najpierw wykonywana jest suma, potem złożenie, a na końcu domknięcie

d)

kolejność operacji jest inna od każdej z wyżej podanych

59.

Dana jest następująca gramatyka G = ({S, A, B}, {a, b, c}, P, S), gdzie:

P:

S → aAB

A → Ab|AaB|b

B → cB|a

Gramatyka jest:

a)

regularna

b)

bezkontekstowa, ale nie jest regularna

c)

kontekstowa, ale nie jest bezkontekstowa

d)

jest gramatyką ogólnego rodzaju, która nie jest gramatyką kontekstową

60.

Wybierz zdanie prawdziwe z niżej podanych

a)

W gramatyce jednoznacznej każde słowo ma tylko jedno wprowadzenie

b)

Dla każdej gramatyki niejednoznacznej istnieje równoważna jej gramatyka jednoznaczna

c)

W gramatyce niejednoznacznej każde słowo ma jedno wyprowadzenie prawostronne i jedno wyprowadzenie lewostronne

d)

W gramatyce jednoznacznej każe słowo ma tylko jedno drzewo wywodu

61.

Wybierz zdanie prawdziwe z niżej podanych

a)

W deterministycznych automatach ze stosem DAZS jest dokładnie jedno przejście z każdego stanu dla danego symbolu wejściowego i symbolu na szczycie stosu

b)

Wartość funkcji przejścia automatu DAZS zależy tylko od stanu i symbolu wejściowego

c)

Wartość funkcji przejścia automatu DAZS zależy tylko od stanu i symbolu na szczycie stosu

d)

Wartość funkcji przejścia automatu DAZS zależy tylko od symbolu wejściowego i symbolu na szczycie stosu

62.

Przedstawiony powyżej wykres składniowy odpowiada następującej produkcji (produkcjom) w zapisie symbolicznym

a)

A → X|Y

b)

A → 0Y|X

c)

A → 0X|Y

d)

A → 0XY

63.

Jeśli język jest rozpoznawany przez pewien automat ze stosem, to jest on

a)

regularny

b)

rekurencyjnie przeliczany, ale nie musi być kontekstowy

c)

bezkontekstowy, ale nie musi być regularny

d)

kontekstowy, ale nie musi być bezkontekstowy

64.

Nieograniczoną taśmę posiada

a)

maszyna Turinga

b)

maszyna Turinga i automat ze stosem

c)

deterministyczny automat ze stosem

d)

niedeterministyczny automat skończony

Similar Resources on Wayground

programaçaõ e robótica

66 questions

programaçaõ e robótica

quiz

Worksheet

•

2nd Grade

Adobe Photoshop - basico, medio e avançado

62 questions

Adobe Photoshop - basico, medio e avançado

quiz

Worksheet

•

1st Grade - University