Matek VII. tétel

Question 1

Lineáris egyenletrendszer

Answer 1

Olyan egyenletrendszer, amelyben az ismeretlenek csak egyszeresen és lineárisan szerepelnek.
Általában Ax=b alakban írható, ahol A egy mátrix, x az ismeretlenek vektora, és b a konstansok vektora.

Question 2

Gauss elimináció

Answer 2

Gauss eliminációval a lineáris egyenletrendszer egy ekvivalens felső trianguláris (vagy Gauss-) alakra hozható, majd visszafelé substitúcióval megoldható.
A módszer során az egyenleteket műveletekkel manipuláljuk, hogy elérjük a trianguláris alakot.

Question 3

Turing-gép

Answer 3

Az Alan Turing által definiált, elvont matematikai modell egy olyan eszközre, amely egy szalagon mozog, olvas és ír a celláin, és állapotok között válthat.
A Turing-gép egy erős számítási modell, amely képes modellezni az összes algoritmust.

Question 4

Algoritmikus eldönthetőség

Answer 4

Egy probléma algoritmikusan eldönthető, ha létezik olyan algoritmus, amely mindig megadja a helyes választ bármilyen bemenet esetén.
Példa: Prímszámok eldöntése algoritmikusan eldönthető

Question 5

Eldönthetetlen problémák

Answer 5

Azok a problémák, amelyekre nincs olyan algoritmus, amely mindig és minden bemenet esetén helyes választ ad.
Példa: Az általános stopprobléma, vagyis nem létezik olyan algoritmus, amely eldöntheti, hogy egy tetszőleges algoritmus végtelenül fut-e vagy sem.

Question 6

Rekurzív nyelv

Answer 6

Egy nyelv rekurzív, ha létezik egy algoritmus, amely el tudja dönteni, hogy egy tetszőleges szóhoz tartozik-e a nyelvhez vagy sem.

Question 7

Rekurzívan felsorolható nyelv

Answer 7

Egy nyelv rekurzívan felsorolható, ha létezik egy olyan Turing-gép, amely minden benne lévő szót egyszer kiír, és leáll, de nem feltétlenül dönti el, hogy egy tetszőleges szóhoz tartozik-e vagy sem.

Question 8

Generatív grammatika

Answer 8

Olyan formális rendszer, amely leírja egy nyelv struktúráját és szabályait.
A generatív grammatika három fő típusa: reguláris, környezetfüggetlen és környezetérzékeny.

Question 9

Nevezetes nyelvosztályok

Answer 9

0. típus (Rekurzívan felsorolható): A Turing-gépek által felismert nyelvek.
1. típus (Környezetérzékeny): A lineárisan elrendezett, neműres nyelvek.
2. típus (Környezetfüggetlen): Az általánosan elfogadott nyelvtanok által generált nyelvek.
3. típus (Reguláris): A véges automaták és reguláris kifejezések által leírt nyelvek.