test kwalifikacyjny na mieszkańca gminy Komorniki

Question 1

Symbole matematyczne

Answer 1

⊆ - inkluzja zbiorów (zawieranie się)

⊂ - właściwe zawieranie się zbiorów

∈ - należy do zbioru

∪ - suma zbiorów

· - konkatenacja

ø- zbiór pusty

Question 2

Koder i dekoder

Answer 2

Koder - gramatyka
Dekoder - automat

Question 3

Problem rozstrzygalny

Answer 3

problem dający się rozstrzygnąć w przeliczalnej liczbie kroków

Question 4

problem efektywnie rozstrzygalny

Answer 4

problem dający się rozstrzygnąć w skończonej liczbie kroków

Question 5

Alfabet

Answer 5

dowolny skończony niepusty zbiór V składający się z liter

Question 6

Słownik

Answer 6

dowolny skończony niepusty zbiór V składający sięze słów

Question 7

Wyrażenie nad V

Answer 7

Dowolny skończony ciąg symboli stworzony z elementów V

Question 8

V* - znaczenie

Answer 8

V* - zbiór wszystkich wyrażeń utworzonych z symboli V

Question 9

V+ - znaczenie

Answer 9

zbiór wszystkich niepustych ciągów symboli z V

Question 10

słowo

Answer 10

zbiór elementów V* utworzony z liter alfabetu V

Question 11

zdanie

Answer 11

zbiór elementów V* utworzonych ze słów słownika V

Question 12

Konkatenacja

Answer 12

łączenie ze sobą wyrażeń;
łączna, ale NIE jest przemienna

Question 13

Porządek leksykograficzny

Answer 13

Porządek w którym słowa układane są zgodnie z kolejnością występowania w alfabecie

Question 14

Język (nad V)

Answer 14

dowolny zbiór słów utworzonych nad alfabetem V

Question 15

Syntaktyka

Answer 15

składnia

Question 16

Semantyka

Answer 16

znaczenie słów

Question 17

Gramatyka generatywna

Answer 17

Uporządkowana czwórka:
G = <Vn, Vt, S, F>

Vn - alfabet symboli nieterminalnych, złożony ze zmiennych syntaktycznych bądź metajęzykowych
Vt - alfabet symboli terminalnych; przedmiotowy
S - symbol początkowy
F -reguły produkcji

Question 18

Język (generowany przez gramatykę G)

Answer 18

L(G) - zbiór słów utworzonych nad alfabetem terminalnym gramatyki G, które są w niej wyprowadzalne z jej symbolu początkowego S

Question 19

Równoważność gramatyk

Answer 19

• gramatyki słabo równoważne: języki generowane przez gramatyki są identyczne
• gramatyki mocno równoważne: gramatyki, które są słabo równoważne i odpowiednie drzewa derywacji są identyczne

Question 20

Operacje na językach

Answer 20

• suma języków L1∪L2
• iloczyn języków L1∩L2
• różnica języków L1\L2
• dopełnienie języka V*\L1
• konkatenacja języków L1L2
• domknięcie Kleene’go
• niepełne domknięcie Kleene’go

Question 21

Operacje regularne na językach

Answer 21

• suma języków
• konkatenacja języków
• domknięcie Kleene’go języka

Question 22

Homomorfizm

Answer 22

Odwzorowanie jednoznaczne, zachowujące konkatenację wyrażeń

Question 23

Znacznik frazowy

Answer 23

Struktura, która reprezentuje składnię wyrażenia w postaci drzewa syntaktycznego.

Każdy wierzchołek drzewa reprezentuje jakąś jednostkę językową, a krawędzie między wierzchołkami ukazują relacje syntaktyczne.

Zwykle reprezentują główne kategorie składniowe

Question 24

Denotacja

Answer 24

Oznaczenie, zakres danej nazwy (zbiór jej desygnatów)

Question 25

Wyrażenie regularne

Answer 25

Syntaktycznie poprawne, zbudowane z symboli ø, λ, *, ∪, (, ) oraz litery alfabetu V Napisy, które opisują wzór według którego można tworzyć słowa należące do języka regularnego

Question 26

Wyrażenia frazowe

Answer 26

grupa słów pełniąca określoną funkcję gramatyczną w zdaniu (np. fraza nominalna, fraza werbalna)

Question 27

Automat skończony

Answer 27

Uporządkowana 5: A= K - niepusty skończony zbiór stanów T - niepusty skończony zbiór zwany alfabetem M - relacja przejścia M: KxT -> K K0 ⊆ K zbiór stanów początkowych automatu H ⊆ K zbiór stanów akceptowalnych

Question 28

Deterministyczny automat skończony

Answer 28

abstrakcyjna maszyna o skończonej liczbie stanów Dla każdego stanu i każdego symbolu wejściowego istnieje dokładnie jedno przejście do stanu następnego, tzn. żew każdym momencie wie jaki stan będzie osiągał po przetworzeniu danego symbolu

Question 29

Niedeterministyczny automat skończony

Answer 29

abstrakcyjna maszyna o skończonej liczbie stanów Dla niektórych stanów może istnieć więcej niż jedno możliwe przejście, lub brak takiego przejścia. Może rozgałęziać się na wiele ścieżek, ale aby zaakceptować wejście, wystarczy, że jedna z tych ścieżek prowadzi do stanu akceptującego

Question 30

FILO

Answer 30

First In Last Out Kartka położona na stos jako pierwsza, zostanie z niego usunięta jako ostatnia

Question 31

LIFO

Answer 31

Last In First Out Kartka położona na stosie jako ostatnia, zostanie z niego usunięta jako pierwsza

Question 32

Automat ze stosem

Answer 32

uporządkowana 7: A= Z - alfabet stosu K - zbiór stanów stosu T - alfabet taśmy wejściowej M - relacja przejścia Z0 - symbol początkowy stosu Q0 - stan początkowy automatu H - zbiór stanów końcowych, akceptowalnych przez automat

Question 33

Symbole

Answer 33

- symbol nieterminalny (pomocniczy, metajęzykowy) - symbol terminalny (przedmiotowy, końcowy) - symbol początkowy (symbol od którego zaczyna się wyprowadzanie wszystkich wyrazów języka) - symbol osiągalny (symbol do którego da się dojść z symbolu początkowego) - symbol nieosiągalny (symbol do którego nie da się dojść z symbolu początkowego) - symbol pasywny (symbol nieterminalny z którego nie da się wyprowadzić żadnego słowa końcowego) - symbol aktywny (symbol nieterminalny z którego da się wyprowadzić słowo końcowe)

Question 34

Hierarchia Chomsky’ego

Answer 34

Dzieli gramatyki ze względu na kształt dopuszczalnych w nich reguł produkcji: - typ 0; gramatyka struktur frazowych - typ 1; gramatyka kontekstowa - typ 2; gramatyka bezkontekstowa - typ 3; gramatyka regularna L3 ⊂ L2 ⊂ L1 ⊂ L0

Question 35

Gramatyka struktur frazowych

Answer 35

Klasa 0 Nie ma żadnych ograniczeń co do reguł produkcji - wszystkie mają kształt P->Q, gdzie P ∈ (Vn ∪ Vt)* Vn(Vn ∪ Vt)*, zaś Q ∈ (Vn ∪ Vt)* Gramatyka struktur frazowych jest równoważna maszynie Turinga

Question 36

Gramatyka kontekstowa (context-sensitive)

Answer 36

Typu 1 Q1AQ2 -> Q1PQ2, gdzie Q1,Q2 ∈ (Vn ∪ Vt)*, A ∈ Vn, P ∈ (Vn ∪ Vt)* \ λ bądź S -> λ, ale wtedy S nie występuje po prawej stronie w żadnej z reguł produkcji Gramatyki kontekstowe odpowiadają automatowi liniowemu ograniczonemu

Question 37

Gramatyka bezkontekstowa (context-free)

Answer 37

Typu 2 Wszystkie z jej reguł produkcji mają kształt A -> P, gdzie A ∈ Vn, a P ∈ (Vn ∪ Vt)* λAλ -> λPλ Odpowiednikiem gramatyki bezkontekstowej jest automat ze stosem

Question 38

Gramatyka regularna

Answer 38

Wszystkie reguły produkcji mają postać A -> P lub A -> PB, gdzie A,B ∈ Vn, zaś P ∈ Vt* Jest równoważna deterministycznemu lub niedeterministycznemu automatowi skończonemu

Question 39

I twierdzenie o postaci normalnej

Answer 39

Dla każdej gramatyki danej klasy i Gi = istnieje równoważna jej gramatyka Gi’ = tej samej klasy taka, że symbole terminalne nie występują po lewej stronie reguł produkcji F’

Question 40

Postać normalna Chomsky’ego

Answer 40

Wszystkie reguły produkcji mają postać: 1) X -> a, gdzie X ∈ Vn, zaś a ∈ Vt lub 2) X -> YZ, gdzie X,Y,Z ∈ Vn Dla każdej bezkontekstowej λ-wolnej gramatyki G, istnieje równoważna jej gramatyka bezkontekstowa w postaci normalnej Chomsky’ego.

Question 41

Gramatyka λ-wolna

Answer 41

Dowolna gramatyka bezkontekstowa jest równoważna pewnej gramatyce kontekstowej o kontekstach pustych (lewym i prawym) Dlatego, każdą gramatykę bezkontekstową można przedstawić jako gramatykę kontekstową

Question 42

Postać normalna Greibach

Answer 42

Każda z reguł produkcji ma postać A -> aX, gdzie A ∈ Vn, a ∈ Vt, X ∈ Vn* Dla każdej λ-wolnej gramatyki bezkontekstowej G, istnieje równoważna jej gramatyka G1 w postaci normalnej Greibach Każda gramatyka w postaci normalnej Greibach jest gramatyką bezkontekstową

Question 43

Postać normalna gramatyk regularnych

Answer 43

Każdy język regularny może być generowany przez gramatykę o regułach następującego kształtu: X -> aY x -> λ gdzie X,Y ∈ Vn, zaś a ∈ Vt

Question 44

Notacja Backusa-Naura (B-N)

Answer 44

Sposób zapisu reguł produkcji gramatyk bezkontekstowych. Opis składni ma postać definicji syntaktycznych, w których występują symbole nieterminalne (pełniące rolę zmiennych metajęzykowych) oraz symbole terminalne. Zmienne metajęzykowe - <> „->” zostaje zastąpione przez „::=” Produkcje o tym samym poprzedniku w zapisie łączy się w jedną, rozdzielając następniki pionową kreską „|” Postać iteracyjna: Ujmujemy pewien napis (wyst po prawej stronie) w nawiasy klamrowe {}. Oznacza to, że taką konstrukcję można zastąpić dowolną, skończoną liczbą powtórzeń napisu ujętego w klamry (w tym zerową liczbę powtórzeń)

Question 45

Postać normalna Kurody

Answer 45

Każda z reguł ma postać: 1) A -> a 2) A -> B 3) A -> BC 4) AB -> CD gdzie a ∈ Vt; A,B, C, D ∈ Vn Dla każdej λ-wolnej gramatyki kontekstowej istnieje równoważna jej gramatyka kontekstowa w postaci normalnej Kurody

Question 46

Postać normalna gramatyki struktur frazowych

Answer 46

Dla każdej gramatyki G typu 0 istnieje równoważna jej gramatyka G’ typu 0 o regułach produkcji następującej postaci: 1) S -> λ 2) A -> a 3) A -> B 4) A -> BC 5) AB -> BC 6) AC -> BC 7) AB -> B gdzie A, B, C ∈ Vn, a ∈ Vt i S jest symbolem początkowym

Question 47

I twierdzenie Kleene’ego

Answer 47

Dla każdego niedeterministycznego automatu A istnieje gramatyka regularna G taka, że L(A)=L(G) Niedeterministyczny automat jest równoważny gramatyce regularnej

Question 48

II twierdzenie Kleene’ego

Answer 48

Dla każdej gramatyki regularnej G istnieje skończony automat A taki, że L(G) = L(A) Gramatyka regularna jest równoważna niedeterministycznemu automatowi skończonemu

Question 49

Twierdzenie Scotta

Answer 49

Dla dowolnego skończonego niedeterministycznego automatu A można skonstruować deterministyczny automat B taki, że A i B są równoważne i TA = TB Przydaje się do tworzenia modeli semantycznych dla języków formalnych

Question 50

Twierdzenie Myhilla

Answer 50

Dla każdej gramatyki regularnej (może niedeterministycznej) istnieje równoważna (generująca ten sam język) jej gramatyka deterministyczna i zupełna Przydaje się do optymalizacji automatu (czyli znalezienia najmniejszego możliwego automatu deterministycznego)

Question 51

Twierdzenie Scotta a Myhilla

Answer 51

Twierdzenie Scotta jest dla automatów skończonych odpowiednikiem twierdzenia Myhilla (używanego do gramatyk regularnych) twierdzenie Myhilla jest używane głównie do analizy i minimalizacji automatycznych reprezentacji języków regularnych, a twierdzenie Scotta służy do formalizacji semantycznych reprezentacji dla tych języków