„Formális nyelv” változatai közötti eltérés

Ugrás a navigációhoz Ugrás a kereséshez
[ellenőrzött változat][ellenőrzött változat]
(→‎Nyelvészeti problémák: kiszámíthatósági és komplexitási elméletek -egyelőre hivatkozzanak a számítógéptudomány cikkre, amíg nem lesz önálló cikkük)
A formális nyelvek definíciója (hogy minden formális nyelv egy univerzum részhalmaza) nyilván általános, de praktikus értelemben használhatatlan definíció (hiszen például egy végtelen számosságú nyelvet nem tudunk kezelni így, nem tudjuk felsorolni az elemeit). A gyakorlati problémák szempontjából fontosabb a generatív nyelvek osztálya; generatív nyelvek azok a nyelvek, amelyekre igaz, hogy van olyan '''nyelvtan''' (más néven '''grammatika'''), ami éppen az ő elemeiket generálja.
 
== NyelvészetiMatematikai-nyelvészeti problémák ==
 
A formális nyelvekkel kapcsolatosan gyakran felmerülő kérdés '''„milyen nehéz eldönteni egy adott szóról, hogy egy adott nyelvhez tartozik-e?”'''
Ez az alapja a [[számítógéptudomány#Története és alágai|kiszámíthatóságelmélet]]nek és [[számítógéptudomány#Története és alágai|bonyolultságelmélet]]nek.
 
További fontos, generatív nyelvekkel kapcsolatos problémák:

Navigációs menü