Jednostranné gramatiky s nahodilým kontextem
| Autor: | Zemek, Petr |
|---|---|
| Jazyk: | angličtina |
| Předmět: |
leftmost derivations
generalized versions forbidding grammars jednostranné gramatiky s nahodilým kontextem normální formy zakazující gramatiky random context grammars povolující gramatiky regulated grammars reduction generativní síla gramatiky s nahodilým kontextem zobecněné verze LL verze formal language theory řízené gramatiky one-sided random context grammars redukce normal forms generative power nejlevější derivace permitting grammars LL versions teorie formálních jazyků |
| Druh dokumentu: | Doctoral Thesis |
| Popis: | Tato disertační práce zavádí jednostranné gramatiky s nahodilým kontextem jako řízené gramatiky založené na bezkontextových gramatikách. V těchto gramatikách je ke každému pravidlu přiřazena množina povolujících symbolů a množina zakazujících symbolů a množina pravidel je rozdělena na množinu levých pravidel s nahodilým kontextem a množinu pravých pravidel s nahodilým kontextem. Levým pravidlem s nahodilým kontextem lze přepsat neterminál pokud se všechny povolující symboly vyskytují vlevo od přepisovaného neterminálu a žádný zakazující symbol tam přítomen není. Pravé pravidlo s nahodilým kontextem lze aplikovat analogicky, ale ona kontrola na přítomnost a nepřítomnost symbolů je provedena doprava od přepisovaného neterminálu. Práce je rozdělena na tři části. První část uvádí motivaci za zavedením jednostranných gramatik s nahodilým kontextem a umisťuje materiál pokrytý v této práci do vědeckého kontextu. Poté dává přehled základů teorie formálních jazyků a některých méně známých oblastí, jejichž znalost je nutná pro pochopení studovaného tématu. Druhá část tvoří jádro práce. Formálně definuje jednostranné gramatiky s nahodilým kontextem a studuje je z mnoha pohledů. Mezi studovaná témata patří generativní síla, vztah k jiným typům gramatik, redukce, normální formy, nejlevější derivace, zobecněné a LL verze těchto gramatiky. Třetí část této práce zakončuje diskusi několika poznámkami. Mezi ně patří poznámky týkající se aplikovatelnosti zavedených gramatik v praxi, bibliografie a otevřených problémů. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|