data science + machine learning & AI Flashcards
wartość 1/8 ma postać w systemie binarnym
1/8 = 0.125
mnożymy przez 2:
0.125•2 = 0.25, 0
0.25•2 = 0.5, 0
0.5•2 = 1, 1
1/8 = 0.001
przykładowo
1/16 = 0.0625
mnożymy przez 2:
0.0625•2 = 0.125, 0
0.125•2 = 0.25, 0
0.25•2 = 0.5, 0
0.5•2 = 1, 1
1/16 = 0.0001
ile informacji zawiera 8 znakowe słowo którego każdy znak jest jedną z liter a, b? Prawdopodobieństwo pojawienia się (niezależnie na każdej pozycji) samogłoski jest dwukrotnie większe od prawdopodobieństwa pojawienia się spółgłoski.
obliczamy pa i pb przy założeniu, że pa=2pb i pa+pb=1
pa = 2/3, pb = 1/3
obliczamy entropię z wzoru H(X) = -pa•log2(pa) - pb•log2(pb) = 0.91
obliczamy ilość informacji z wzoru
info = H(X)•n = 0.91•8 = 7.28 bitów
algorytm to:
Algorytm to skończony ciąg jasno określonych instrukcji lub kroków, które prowadzą do rozwiązania określonego problemu lub wykonania zadania. Kluczowe cechy: skończoność, precyzyjność, wejście, wyjście, efektywność, uniwersalność. Uporządkowany zbiór operacji
język formalny jest:
podzbiór zbioru wszystkich słów nad skończonym alfabetem
syntaktyka języka programowania opisuje:
zasady i reguły dotyczące poprawnej struktury kodu źródłowego napisanego w tym języku. Innymi słowy, syntaktyka definiuje, jak należy pisać instrukcje i jak je organizować, aby były one zrozumiałe dla kompilatora lub interpretera danego języka programowania. Syntaktyka obejmuje składnię, czyli sposób, w jaki symbole, słowa kluczowe i konstrukcje są używane do tworzenia poprawnych programów.
semantyka języka programowania:
definiuje precyzyjnie znaczenie poszczególnych symboli oraz ich funkcję w programie
nawiasy <> w notacji EBNF oznaczają
służą do oznaczania nieterminalnych symboli. Ułatwiają rozróżnienie między nieterminalnymi i terminalnymi symbolami w definicjach gramatyki. Pomagają w czytelności i organizacji reguł gramatycznych.
kodem ASCII możemy zakodować:
dowolny znak z zakresu 0-127 (7 bitowy kod)
kodowanie znaków metodą UTF-8
pozwala zakodować dowolne znaki UNICODE
od czego zależy dokładność liczb zmiennopozycyjnych w komputerze?
od rozmiaru mantysy
rozmiar bitowy pola mantysy wpływa na dokładność zapisu liczb w formacie zmiennoprzecinkowym
cechami kodu uzupełnień do dwóch są:
jednoznaczna reprezentacja 0
łatwe negowanie liczb
jednoznaczna reprezentacja liczb ujemnych i dodatnich: MSB to 0 albo 1
symetryczny zakres liczb: kod uzupełnień do dwóch dla liczby dodatniej jest taki sam jak jej reprezentacja binarna bez znaku.
proste operacje arytmetyczne
wykrywanie przepełnienia
kolejność bitów
dana jest następująca reprezentacja liczb zmiennopozycyjnych: Mantysa zajmuje 20 bitów, wykładnik zajmuje 8 bitów; Wykładnik i mantysa zapisywane są w kodzie U2; Przecinek leży na lewo od mantysy; Z dokładnością do ilu cyfr dziesiętnych można pamiętać liczby w tej reprezentacji?
mantysa zajmuje 20 bitów w kodzie U2, więc pierwszym bitem jest bit znaku, więc 19 określa wartość mantysy
wykładnik zajmuje 8 bitów
zakres liczb zmiennopozycyjnych jest określony przez wartości wykładnika i mantysy, dla 8-bitowego wykładnika zakres jest szeroki, ale istotna jest precyzja reprezentacji zależąca od liczby bitów mantysy
liczbę bitów mantysy n można przeliczyć na liczbę cyfr dziesiętnych d=log10(2n)=nlog10(2)
dla n = 19: d=19•log10(2)=19•0.3010 = 5.72, więc z dokładnością do ok. 5-6 cyfr dziesiętnych
dana jest następująca reprezentacja liczb zmiennopozycyjnych: Mantysa zajmuje 22 bity w tym bit znaku, cecha zajmuje 10 bitów w tym bit znaku. Cecha i mantysa zapisywane są w kodzie U2. Przecinek leży na lewo od mantysy (mantysa jest ułamkiem [1/2..1]). Jaka jest największa możliwa liczba w tym systemie?
mantysa 22 bity (1 bit znaku)
xmax=MmaxB^Emax=(B-B^-(m-1))B^Emax < B^Emax+1
B to podstawa systemu liczbowego (u nas 2)
M mantysa
Emax maksymalna wartość wykładnika, czyli 2^n-1
xmax=(2-2^-(22-1))2(2^9-1)=(2-2^-21)2^511=2^512-2^-490=1.34 razy 10^154
minimalna liczba bitów niezbędna by reprezentować liczby zmiennopozycyjne z zakresu -10^6…10^6 z dokładnością do 2 miejsc znaczących to:
8 bitów
liczba 10010 reprezentowana w systemie U2 ma wartość:
najistotniejszy bit to 1, więc jest ujemna
10010=-2^4+2^1=-16+2=-14
w standardzie IEEE 754 dla liczb zmiennopozycyjnych podwójnej precyzji ile bitów zajmuje mantysa, wykładnik
łącznie 64 bity: mantysa 52 bity, wykładnik 11 bitów, znak liczby 1 bit
bramki logiczne wykonują operacje na:
sygnałach binarnych
(wejściach/układach scalonych/układach cyfrowych)
bramka logiczna NAND wykonuje
wykonuję operację AND, a następnie NOT odwracając wynik
zbiór przerzutników służących do przechowywania informacji cyfrowej to
rejestr
do czego służy stos systemowy?
Do przechowywania zmiennych lokalnych
Stosowany jest przez procesory do chwilowego zapamiętywania rejestrów procesora, do przechowywania zmiennych lokalnych, a także w programowaniu wysokopoziomowym.
liczby stałopozycyjne w komputerze są reprezentowane w kodzie uzupełnień do 2. Dla jakich wartości funkcja abs(x) będzie obliczona prawidłowo?
liczb -127 do 127 (poza -128 bo nie da się zaprezentować 128)
zmienna typu wskaźnik zajmuje 4 bajty. Ile pamięci można zaadresować takim wskaźnikiem?
1 bajt = 8 bitów
wskaźnik ma 4 bajty, więc 4*8=32 bity
za pomocą 32-bitowego wskaźnika można zaadresować 2^32 różnych lokalizacji pamięci, czyli 4 294 967 296 bajtów, czyli około 4GB
jeżeli w programie następuje odwołanie poza obszar tablicy
nieprzewidywalne zachowanie, segmentation fault, przepełnienie bufora, błąd odczytu lub zapisu, nieeoczekeiwane wyniki, błąd wykonania Runtime Error, Index Error, wycieki pamięci
których nawiasów trzeba użyć w Odwrotnej Notacji Polskiej do zmiany kolejności wykonywania działań?
nie trzeba ; )
jaki wynik da następujące wyrażenie zapisane w ONP : 2 3 4 5 + * +
rozpoczynamy od pustego stosu, iterujemy po kolejnych elementach wyrażenia, napotykając liczbę umieszczamy ją w stosie, jeśli napotkamy operator, pobieramy elementy stosu, wykonujemy działanie i wkładamy wynik do stosu
Napotykamy 2: [2]
Napotykamy 3: [2, 3]
Napotykamy 4: [2, 3, 4]
Napotykamy 5: [2, 3, 4, 5]
Napotykamy +: Pobieramy ostatnie elementy stosu, wynik umieszczamy na stosie: 4+5=9: [2, 3, 9]
Napotykamy mnożenie: 9razy3=27: [2, 27]
Napotykamy +: 2+27=29: [29]
Wynik znajduje się na szczycie stosu: 29
co oznacza, że algorytm sortowania tablicy posiada złożoność O(n^2)
wykonywana liczba porównań elementów wynosi n^2
przykłady algorytmów sortowania o złożoności O(n2):
Sortowanie bąbelkowe (Bubble Sort)
Sortowanie przez wstawianie (Insertion Sort)
Sortowanie przez wybieranie (Selection Sort)
jeżeli elementy w tablicy są posortowane, to możliwe jest wyszukiwanie
wyszukiwanie binarne, interpolacyjne, Fibbonaci search (sekwencyjne też, ale nie jest optymalne?)
przy rozmieszczaniu algorytmicznym w tablicy z haszowaniem kolizja adresowa może wystąpić gdy
kolizja adresowa w algorytmach haszowania występuje, gdy dwa różne klucze mapują się do tego samego indeksu w tablicy haszowej.
- funkcja haszująca przypisuje różnym kluczom ten sam indeks w tablicy haszowej (dwa klucze przypadają na to samo miejsce)
- funkcja haszująca daje ten sam wynik dla dwóch kluczy
- dwa klucze są przetwarzane przez funkcję haszującą
najszybsza metoda sortowania oparta o porównywanie kluczy posiada złożoność:
NlogN, liniowo-logarytmiczną
ekstensywna metoda sortowania:
to taka, w której potrzeba dodatkowej pamięci
stabilną metodą sortowania jest
Bubble sort (wszystkie), Insertion i Binary insertion sort, Merge sort, Counting sort, Radix sort
które metody sortowania mają złożoność O(NlogN)
sortowanie szybkie - QuickSort (O(NlogN) to średnia złożoność, w najgorszym przypadku O(N^2)
sortowanie przez scalanie - MergeSort
sortowanie kopcowe - HeapSort
które metody sortowania mają złożoność O(N )
sortowanie kubełkowe - Bucket Sort
sortowanie pozycyjne - Radix Sort
sortowanie przez zliczanie - Counting Sort
które metody sortowania mają złożoność O(N^2)
sortowanie bąbelkowe - Bubble Sort
sortowanie przez wybieranie - Selection Sort
sortowanie przez wstawianie - Insertion Sort (w najgorszym ma O(N^2), ale w najlepszym może osiągnąć O(N)
sortowanie przez łopatkowanie - Gnome Sort
sortowanie szybkie - Quick Sort
drzewo BST jest drzewem AVL gdy:
drzewo AVL jest drzewem BST, w którym dla każdego węzła wysokość jego poddrzew dla lewego i prawego syna różni się co najwyżej o 1
dla każdego wierzchołka wysokości (rozmiary? może) jego poddrzew różnią się co najwyżej o 1
drzewo binarne pełne o N poziomach posiada:
Dla pełnego drzewa binarnego o N poziomach istnieje 2^N-1 węzłów/wierzchołków
(Dla n węzłów liczba poziomów jest równa log2(n+1))
jeżeli w drzewie binarnym nie występuje wskazanie na ojca to:
nie ma ojca i jesteś korzeniem i nie ma go wskazanego albo niemożliwe jest przeglądanie z dołu do góry, bo nie wiadomo kim jest ojciec
złożoność wyszukiwania w drzewie AVL jest:
(odp. podana: liniowa ze względu na liczbę poziomów)
własności drzewa AVL gwarantują, że pesymistyczny czas wyszukiwania elementu w drzewie o n węzłach wynosi 1.44(log2n) (logn), podczas gdy dla niezrównoważonego BST (w postaci listy) czas ten wynosi n.
drzewo rozpinające graf zawiera:
wszystkie wierzchołki grafu
ile cykli Hamiltona posiada graf pełny o N wierzchołkach?
każdy graf pełny o N wierzchołkach zawiera N! cykli Hamiltona, gdyż dla każdej permutacji indeksów wierzchołków n1, n2, …, nN, n1 wyznacza istniejącą drogę, będącą cyklem Hamiltona
dana jest następująca reprezentacja liczb zmiennopozycyjnych: Mantysa zajmuje 16 bitów, wykładnik zajmuje 8 bitów; Wykładnik i mantysa zapisywane są w kodzie U2; Przecinek leży na lewo od mantysy; Z dokładnością do ilu cyfr dziesiętnych można pamiętać liczby w tej reprezentacji?
między 4 a 5
dokładność reprezentacji zmiennoprzecinkowej jest określona przez:
liczbę dostępnych bitów mantysy
wyrażenie Boolowskie może być zrealizowane z:
NAND i NOR
niech P (A) = 1/2 i P (B) = 3/4. P (A|B) może być równe:
P(A∣B)=P(A∩B)/P(B)
P(A∩B)=P(A∣B)⋅P(B), P(A) = ½, P(B)=¾
P(A∩B) musi być mniejsze lub równe P(B), bo prawdopodobieństwo nie może być większe niż 1 i prawdopodobieństwo zajścia A pod warunkiem B nie może być większe niż prawdopodobieństwo zdarzenia B
Pierwszy przypadek:
P(A∩B) = P(B), więc P(A|B) = 1
Drugi przypadek:
P(A∩B) = 0, więc P(A|B) = 0
Odpowiedzi mogą być z przedziału [0,1]
trzy ściany kostki czworościennej (w kształcie czworościanu foremnego) zostały pomalowane na, odpowiednio, biało, czerwono i zielono. Czwarta została pomalowana w biało–czerwono–zielone pasy. Doświadczenie polega na rzucaniu kostki na płaszczyznę i obserwowanie koloru ściany, na którą upadła. Zdarzenie B oznacza upadek na ścianę z kolorem białym, C — upadek na ścianę z kolorem czerwonym, a Z — upadek na ścianę z kolorem zielonym. Zdarzenia B, C i Z:
nie są niezależne
czułością testu diagnostycznego nazywa się prawdopodobieństwo uzyskania wyniku pozytywnego (czyli stwierdzenia choroby) u osoby chorej, natomiast swoistością testu nazywa się prawdopodobieństwo uzyskania wyniku negatywnego u osoby zdrowej. Czułość testu wykrywającego chorobę X wynosi 80%, a jego swoistość 70%. Na X cierpi 10% populacji. Test wykonany na Ryszardzie dał wynik pozytywny. Prawdopodobieństwo tego, że Ryszard jest chory:
- chorzy stanowią 10% populacji, zdrowi 90%
- czułość testu 80%, B1 - wynik pozytywny u osoby chorej
- swoistość testu 70%, B2 - wynik negatywny u osoby zdrowej
P(A) prawdopodobieństwo tego, że Ryszard jest chory, D - pozytywny wynik testu ogółem
liczymy P(A|D) prawdopodobieństwo tego, że Ryszard jest chory pod warunkiem, że dostał wynik pozytywny
P(D) = 0.80.1 + 0.30.9 (wynik pozytywny u chorej * ilość chorych + wynik pozytywny u osoby zdrowej * ilość zdrowych)
P(A|D) = P(AiD)/P(D)=(0.80.1)/(0.80.1 + 0.3*0.9)= (0,08)/(0,08+0,27)= (0,08)/(0,35)= 0,229
bliźnięta jednojajowe stanowią około 8% wszystkich bliźniąt. Elvis Presley miał brata bliźniaka, który umarł przy urodzeniu. Prawdopodobieństwo tego, że Elvis był bliźniakiem jednojajowym:
jest równe 0.08
albo 0.15, bo 8/46+8
mamy 2 pudełka ciastek. Pudełko 1 zawiera 10 ciastek z czekoladą i 30 bez, a pudełko 2 zawiera po 20 ciastek obu rodzajów. Losujemy (z równym prawdopodobieństwem) jedno z pudełek, a następnie losujemy (również z równym prawdopodobieństwem) jedno ciastko z wylosowanego pudełka. Wylosowane ciastko jest bez czekolady. Prawdopodobieństwo tego, że ciastko pochodzi z pudełka 1:
B1: wylosowano pudełko 1
B2: wylosowano pudełko 2
A: wylosowano ciastko bez czekolady
P(B1|A) prawdopodobieństwo, że ciastko pochodzi z pudełka 1 pod warunkiem, że zostało wylosowane ciastko bez czekolady
P(B1) = P(B2) = ½
Prawdopodobieństwo wylosowania ciastka bez czekolady z pudełka 1 (ciastek bez czekolady jest 30 i z czekoladą 10, więc razem to 40) P(A|B1) = ¾
Prawdopodobieństwo wylosowania ciastka bez czekolady z pudełka 2 (ciastek bez czekolady jest 20 i z czekoladą 20, więc razem to 40) P(A|B2) = ½
Całkowite prawdopodobieństwo P(A) = P(A|B1)P(B1) + P(A|B2)P(B2)
P(A) = ¾ * ½ + ½ * ½ = ⅜ +¼ = ⅝
Z twierdzenia Bayesa:
P(B1|A) = P(A|B1)P(B1)/P(A) = ¾ *½ / ⅝ = ⅜ / ⅝ = ⅗
Prawdopodobieństwo wynosi ⅗ , więc 0.6
niech X będzie zmienną losową równą bezwzględnej wartości różnicy liczby oczek w rzucie dwoma kostkami symetrycznymi. Wartość oczekiwana X:
aby obliczyć wartość oczekiwaną E(X) zmiennej losowej X, która jest równą bezwzględnej wartości różnicy liczby oczek w rzucie dwoma symetrycznymi kostkami, należy najpierw wyznaczyć wszystkie możliwe wartości X oraz ich prawdopodobieństwa.
X - bezwzględna różnica między liczbą oczek
X:{0,1,2,3,4,5}
dla X=0, (1,1),(2,2),(3,3),(4,4),(5,5),(6,6)
P(X=0) = 6/36 = ⅙
dla X=1 (1,2),(2,1),(2,3),(3,2),(3,4),(4,3),(4,5),(5,4),(5,6),(6,5)
P(X=1) = 10/36 = 5/18
dla X=2 (1,3),(3,1),(2,4),(4,2), (3,5),(5,3),(4,6),(6,4)
P(X=2) = 8/36 = 2/9
dla X=3 (1,4),(4,1),(2,5),(5,2),(3,6),(6,3)
P(X=3) = 6/36 = ⅙
dla X=4 (1,5),(5,1),(2,6),(6,2)
P(X=4) = 4/36 = 1/9
dla X=5 (1,6),(6,1)
P(X=5) = 2/36 = 1/18
E(X) jest sumą iloczynów wartości X oraz jej prawdopodobieństwa
E(X) = 0⅙+15/18+22/9+3⅙+41/9+51/18 = 0 + 5/18 + 4/9 + ½ + 4/9 + 5/18 = 35/18 = 1.94
jest mniejsza od 2
niech X będzie zmienną losową równą większej z wyrzuconych liczb oczek w rzucie dwoma kostkami symetrycznymi. Mediana X:
5 (z łapy)
które z poniższych rozkładów są rozkładami dyskretnymi?
Rozkłady dyskretne:
- Rozkład jednostajny dyskretny (discrete uniform distribution)
- Rozkład Bernoulliego (Bernoulli distribution
- Rozkład dwumianowy (binomial distribution)
- Rozkład Poissona (Poisson distribution)
- Rozkład geometryczny (geometric distribution)
- Rozkład hipergeometryczny (hypergeometric distribution)
niech zmienna losowa modeluje liczbę goli strzelaną przez (ustaloną ale dowolną) drużyną piłkarską w każdym meczu. Który z rozkładów może sensownie być rozważany jako rozkład tej zmiennej?
(podana odp.: normalny)
Poissona
które z poniższych rozkładów są symetryczne?
standardowy rozkład normalny (Gaussa), równomierny, Cauchy’ego, na sferze, LaPlace’a, dwumianowy
rozkładem odniesienia przy konstrukcji testów istotności współczynników prostej regresji liniowej oraz przy konstrukcji przedziałów ufności dla tych współczynników jest:
test t-Studenta
w modelu liniowym Y = β0+β1X+c do oceny istotności wpływu predyktora X na zmienną odpowiedzi Y stosuje się testy odpowiednich hipotez statystycznych, w ramach których oblicza się p-wartości. Dla których z poniższych p-wartości można uznać, że X ma istotny wpływ na Y ?
p-value: weryfikuje czy współczynnik kierunkowy b, jest istotnie różny od 0. Sprawdza on sensowność zastosowania funkcji regresji i czy, w ogóle zmiana jednej wartości, pociągnie zmianę drugiej. Szukamy wartości poniżej poziomu istotności, najlepiej tych bliskich zeru.
niski poziom p-value odrzuca hipotezę mówiącą o braku związku pomiędzy wartościami. Progiem, jaki się zazwyczaj przyjmuje (zwanym poziomem istotności) jest wartość około 0.05. Wartość p-value jest szczególnie istotna dla regresji z wieloma zmiennym. W naszym przypadku najczęściej jest to kwestia widoczna na pierwszy rzut oka.
jeżeli p <= alfa to odrzucamy H0
jeżeli p > alfa to nie ma podstaw do odrzucenia
do oceny dopasowania modelu liniowego stosuje się statystyki RSE (rezydualny błąd standardowy) i R2 (proporcja wyjaśnionej wariancji). Które z poniższych zestawów wartości wskazują na model dobrze dopasowany?
RSE - jak najbliżej 0, R2 - jak najbliżej 1
RSE to miara reszt, czyli różnicy między wartościami rzeczywistymi a wartościami przewidywanymi przez model. Im mniejsza wartość RSE, tym lepiej model pasuje do danych. Idealnie dopasowany model miałby RSE równy 0, co oznaczałoby, że model dokładnie przewiduje wartości obserwowane.
R2 mierzy, jak duża część zmienności w danych jest wyjaśniana przez model. Im większa wartość R2, tym lepiej model pasuje do danych. R2 równy 1 oznaczałby, że model doskonale dopasowuje się do danych, tzn. wszystkie zmienności w danych są wyjaśniane przez model. Natomiast R2 równy 0 oznaczałby, że model nie wyjaśnia zmienności w danych i nie pasuje w ogóle.
wiemy, że zdanie: ”Jeśli Jan jest informatykiem, to jeśli nie chodzi do pracy, to nie zarabia” jest fałszywe. Która z odpowiedzi jest poprawna?
zdanie w postaci logicznej: (P → (Q→R))
P: Jan jest informatykiem
Q: Jan nie chodzi do pracy
R: Jan nie zarabia
Implikacja (P → (Q→R)) jest fałszywa tylko jeżeli P jest prawdziwe, a Q→R jest fałszywe. Q→R jest fałszywe tylko jeżeli Q jest prawdziwe i R jest fałszywe
Wynika z tego, że:
P: Jan jest informatykiem
Q: Jan nie chodzi do pracy
R: Jan zarabia
Z podanej informacji wynika, że Jan jest informatykiem, nie chodzi do pracy, ale mimo to zarabia.
w pewnym miasteczku mieszkańcy dzielą się na dwie kategorie: jedni zawsze mówią prawdę, drudzy zawsze kłamią. Spotykamy parę tubylców A i B. Na nasze pytanie, do jakiej kategorii mieszkańców należą, A odpowiada: ”Nieprawda, że co najwyżej jeden z nas jest kłamcą”. Kogo właściwie spotkaliśmy?
X - co najwyżej 1 z nas jest kłamcą
1. przypadek: A mówi prawdę
X = (AiB) lub (Ai~B)
~X = ~(AiB) i ~(Ai~B)
~X = (~A lub ~B) lub (~A lub B)
czyli w każdym przypadku 0 bo ~A=0
- przypadek 2: A kłamie
X = (~AiB) lub (AiB)
~A
A kłamie i B mówi prawdę
ilu podziałów punktów na grupy zostanie dokonanych w metodzie FFT dla 16 punktów:
Jeżeli mamy N=16 punktów, to liczba podziałów będzie równa logarytmowi o podstawie 2 z liczby punktów, czyli: log2(N)= log2(16) = 4
W skrócie dzielimy do uzyskania pojedynczych punktów:
16/2=8
8/2=4
4/2=2
2/2=1
dla trzeciego podziału na grupy w metodzie FFT:
numery punktów w tej samej grupie mają taką samą resztę przy dzieleniu przez 2
dopełnieniem języka ab* jest:
ab°a(a|b)° suma b(a|b)°
wybierz prawdziwe stwierdzenia odnośnie automatów Rabina-Scotta, Moore’a i Mealy’ego:
Mealy (niepuste), Moore (akceptuje puste), Rabin-Scott (akceptuje puste)
języki regularne, czytają słowo do końca, są skończone
Automat Mealy’ego NIE akceptuje słowa pustego. Dowodzi się, że automat Mealy’ego jest równoważny automatowi Moore’a (z wyjątkiem akceptacji słowa pustego). Dowodzi się dalej, że automat Moore’a jest równoważny deterministycznemu automatowi Rabina-Scotta (czyli też akceptuje puste słowa).
Wszystkie automaty akceptują wyłącznie języki regularne. Wszystkie czytają słowo wejściowe do końca (są deterministyczne i zupełne). Decyzja o akceptacji zależy od ostatniego zapisanego na taśmie wyjściowej symbolu (aut. Moore’a i Mealy) lub od stanu, w którym automat zatrzyma się (aut. Rabina-Scotta).
problem przynależności słowa do języka, tj. x ∈ L ?, jest problemem rozstrzygalnym dla klasy języków:
regularnych, bezkontekstowych, kontekstowych
problem jednoznaczności danej gramatyki G jest problemem rozstrzygalnym dla klasy języków:
regularnych
problem pustości języka, tj. L(G) = ∅ ?, jest problemem rozstrzygalnym dla klasy języków:
regularnych, bezkontekstowych
