One-Side Pumping and Two-Side Pumping by Complete CF(¢, $)-grammars

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F23%3A00369658" target="_blank" >RIV/68407700:21230/23:00369658 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216208:11320/23:10477033

Výsledek na webu

<a href="https://ceur-ws.org/Vol-3498/paper14.pdf" target="_blank" >https://ceur-ws.org/Vol-3498/paper14.pdf</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

One-Side Pumping and Two-Side Pumping by Complete CF(¢, $)-grammars

Popis výsledku v původním jazyce

We introduce context-free grammar with sentinels, CF(¢, $)-grammar, as a generalization of recently introduced LR(¢, $)grammar. Original LR(¢, $)-grammars can be used to construct deterministic pumping restarting automata performing correctness and error preserving pumping analysis by reduction on each word over its input alphabet. Pumping analysis by reduction involves step-wise simplification of an input word by removing at most two continuous parts of the current word while preserving the correctness or incorrectness of the word. Each such simplification step corresponds to removing portions of the current word that can be “pumped” according to the pumping lemma for context-free languages, and thus, it does not use any nonterminals. One-side pumping grammars are CF(¢, $)-grammars that allow removing just one continuous part in each step of pumping reduction. A complete CF(¢, $)-grammar generates both a language and its complement with sentinels. We show that complete one-side pumping CF(¢, $)-grammars characterize the class of regular languages, while LR(¢, $)-grammars that allow two-side pumping reductions characterize the class of deterministic context-free languages. LR(¢, $)-grammars that do not allow any one-side pumping reduction generate non-regular languages only.

Název v anglickém jazyce

One-Side Pumping and Two-Side Pumping by Complete CF(¢, $)-grammars

Popis výsledku anglicky

We introduce context-free grammar with sentinels, CF(¢, $)-grammar, as a generalization of recently introduced LR(¢, $)grammar. Original LR(¢, $)-grammars can be used to construct deterministic pumping restarting automata performing correctness and error preserving pumping analysis by reduction on each word over its input alphabet. Pumping analysis by reduction involves step-wise simplification of an input word by removing at most two continuous parts of the current word while preserving the correctness or incorrectness of the word. Each such simplification step corresponds to removing portions of the current word that can be “pumped” according to the pumping lemma for context-free languages, and thus, it does not use any nonterminals. One-side pumping grammars are CF(¢, $)-grammars that allow removing just one continuous part in each step of pumping reduction. A complete CF(¢, $)-grammar generates both a language and its complement with sentinels. We show that complete one-side pumping CF(¢, $)-grammars characterize the class of regular languages, while LR(¢, $)-grammars that allow two-side pumping reductions characterize the class of deterministic context-free languages. LR(¢, $)-grammars that do not allow any one-side pumping reduction generate non-regular languages only.

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

<a href="/cs/project/GA19-21198S" target="_blank" >GA19-21198S: Složité predikční modely a jejich učení z částečně anotovaných dat</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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 of the 23rd Conference Information Technologies – Applications and Theory (ITAT 2023)

ISBN

—

ISSN

1613-0073

e-ISSN

1613-0073

Počet stran výsledku

11

Strana od-do

110-120

Název nakladatele

CEUR Workshop Proceedings

Místo vydání

Aachen

Místo konání akce

Tatranské Matliare

Datum konání akce

22. 9. 2023

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

WRD - Celosvětová akce

Kód UT WoS článku

—