Bezkonteksta valodas un to ģenerējošas funkcijas

2006

Darba galvenais mērķis bija savākt informāciju par bezkonteksta valodām un to ģenerējošam funkcijām viena valodā (šeit latviešu valoda). Darbā apskatītas bezkonteksta valodas, bezkonteksta gramatikas, ģenerējošo funkciju un magazīnas automātu jēdzieni. Ir apskatītas arī ar to saistītas teorēmas, lemmas un to pierādījumi. Darbā vēl ir apskatīti ģenerējošo funkciju pielietojumi, lai atrisinātu bezkonteksta valodu algoritmiskās problēmas, tādas kā bezkonteksta gramatikas izvedamo vārdu skaits vārda garumam n; ja kādai valodai ir viennozīmīga gramatika, vai cita gramatika, kura ģenerē to pašu valodu, ir viennozīmīga; vai ir atrisināma viennozīmīgas gramatikas ģenerētas valodas un automāta valod…