| Meno: | Michal
|
|---|
| Priezvisko: | Borga
|
|---|
| Názov: | Vlastnosti bezkontextových grafových jazykov
|
|---|
| Vedúci: | prof. RNDr. Branislav Rovan, PhD.
|
|---|
| Rok: | 2008
|
|---|
| Blok: | APV
|
|---|
| Kľúčové slová: | grafové gramatiky, usmerňovanie odvodenia, blokujúce hrany, konfluentnosť
|
|---|
| Abstrakt: | V práci sa zaoberáme skúmaním vlastností a porovnávaním rôznych typov
NCE a NLC grafových jazykov. Predstavíme si analogické aj kontrastné
vlastnosti niektorých tried grafových jazykov v porovnaní s jazykmi nad reťazcami. Napríklad si ukážeme, že bezkontextové grafové jazyky spĺňajú vlastnosti pumpovacej lemy pre bezkontextové jazyky nad reťazcami, čo sa
týka ich hustoty slov v jazyku. A naopak ukážeme, že bezkontextové grafové jazyky nemôžu obsahovať všetky grafy nad danými abecedami uzlov a hrán.
|
|---|