On LL(k) linear conjunctive grammars

Linear conjunctive grammars are a family of formal grammars with an explicit conjunction operation allowed in the rules, which is notable for its computational equivalence fo one-way real-time cellular automata, also known as trellis automata. This paper investigates the LL(\(k\)) subclass of linear...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-12
Main Authors: Olkhovsky, Ilya, Okhotin, Alexander
Format: Article
Language:English
Subjects:
Cellular automata
Grammars
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Linear conjunctive grammars are a family of formal grammars with an explicit conjunction operation allowed in the rules, which is notable for its computational equivalence fo one-way real-time cellular automata, also known as trellis automata. This paper investigates the LL(\(k\)) subclass of linear conjunctive grammars, defined by analogy with the classical LL(\(k\)) grammars: these are grammars that admit top-down linear-time parsing with \(k\)-symbol lookahead. Two results are presented. First, every LL(\(k\)) linear conjunctive grammar can be transformed to an LL(1) linear conjunctive grammar, and, accordingly, the hierarchy with respect to \(k\) collapses. Secondly, a parser for these grammars that works in linear time and uses logarithmic space is constructed, showing that the family of LL(\(k\)) linear conjunctive languages is contained in the complexity class \(L\).
ISSN:2331-8422