Április 22. kedden, 12.30 órai kezdettel a Matematika és Informatika Intézet intézeti tárgyalóban A párhuzamosság megjelenési formái a Chomsky-féle nyelvtípusoknál címmel elõadást tart Dr. habil Nagy Benedek (Debreceni Egyetem, Informatikai Kar) Cim: A klasszikus formális nyelvek elmélete a múlt század 60-as éveiben alakult ki, fõképpen N. Chomsky akkori munkásságának köszönhetõen. A generatív nyelvtanok ekvivalensek a Turing-gépek által definiált kiszámíthatósággal. A
számítástudományban ugyancsak régen megjelentek különbözõ párhuzamos számítási modellek, amelyek az utóbbi évtizedekben egyre nagyobb súlyt kapnak a gyakorlatban is.
Az elõadás során arra szeretnénk rávilágítani, hogy a Chomsky-féle nyelvosztályokhoz kötõdõen mit mondhatunk a
párhuzamosságról. Hogyan, milyen formában jelenhet meg a párhuzamosság a nyelvtanokhoz kötõdõ levezetésekben, illetve az elfogadó-automaták mûködését tekintve. A reguláris kifejezésekben az unió mûvelet segítségével tudunk valamiféle párhuzamosságot értelmezni. Itt új eredményként normál formát, illetve az unió-bonyolultság fogalmát vezetjük be. A reguláris nyelveket a véges automaták fogadják el.
Ezeknek egyfajta kiterjesztését mutatjuk be, amikben két olvasó fej a szalagon levõ szó két végérõl indulva párhuzamosan végzi a beolvasást.
Ezekkel az automatákkal a lineáris, és a páros-lineáris nyelveket jellemezzük.
A környezetfüggetlen nyelvtanok a levezetésben egyféle maximális párhuzamosságot engednek meg. Ez jelentheti pl. a levezetési fák felépítését oly módon, hogy minden lépésben egy teljes új szint jelenik meg. A környezetfüggõ nyelvtanoknál az egyoldalú normál-formából kiindulva a levezetéseket fához hasonló gráfokkal reprezentálhatjuk, itt a levezetésekben a párhuzamosság már szinkronizált kell hogy legyen egyes (szomszédos) ágak között.