Final sentential forms

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F23%3APU149400" target="_blank" >RIV/00216305:26230/23:PU149400 - isvavai.cz</a>

Výsledek na webu

<a href="https://arxiv.org/abs/2309.08719v1" target="_blank" >https://arxiv.org/abs/2309.08719v1</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4204/EPTCS.388.6" target="_blank" >10.4204/EPTCS.388.6</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Final sentential forms

Popis výsledku v původním jazyce

Let G be a context-free grammar with a total alphabet V, and let F be a final language over an alphabet W as a subset of V. A final sentential form is any sentential form of G that, after omitting symbols from V-W, it belongs to F. The string resulting from the elimination of all nonterminals from W in a final sentential form is in the language of G finalized by F if and only if it contains only terminals. The language of any context-free grammar finalized by a regular language is context-free. On the other hand, it is demonstrated that L is a recursively enumerable language if and only if there exists a propagating context-free grammar G such that L equals the language of G finalized by {w#rev(w):string w over alphabet {0,1}}, where rev(w) is the reversal of w.

Název v anglickém jazyce

Final sentential forms

Popis výsledku anglicky

Let G be a context-free grammar with a total alphabet V, and let F be a final language over an alphabet W as a subset of V. A final sentential form is any sentential form of G that, after omitting symbols from V-W, it belongs to F. The string resulting from the elimination of all nonterminals from W in a final sentential form is in the language of G finalized by F if and only if it contains only terminals. The language of any context-free grammar finalized by a regular language is context-free. On the other hand, it is demonstrated that L is a recursively enumerable language if and only if there exists a propagating context-free grammar G such that L equals the language of G finalized by {w#rev(w):string w over alphabet {0,1}}, where rev(w) is the reversal of w.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings 13th International Workshop on Non-Classical Models of Automata and Applications

ISBN

—

ISSN

2075-2180

e-ISSN

—

Počet stran výsledku

9

Strana od-do

38-47

Název nakladatele

School of Computer Science and Engineering, University of New South Wales

Místo vydání

Famagusta

Místo konání akce

Famagusta, Cyprus

Datum konání akce

18. 9. 2023

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—