“Conjunctive grammar”的意思、由来-开放百科全书

词条

Conjunctive grammar

释义

Formal definition
Definition by derivation Example
Parsing algorithms
Theoretical properties
Synchronized alternating pushdown automata
References
External links

Conjunctive grammars are a class of formal grammars

studied in formal language theory.

They extend the basic type of grammars,

the context-free grammars,

with a conjunction operation.

Besides explicit conjunction,

conjunctive grammars allow implicit disjunction

represented by multiple rules for a single nonterminal symbol,

which is the only logical connective expressible in context-free grammars.

Conjunction can be used, in particular,

to specify intersection of languages.

A further extension of conjunctive grammars

known as Boolean grammars

additionally allows explicit negation.

The rules of a conjunctive grammar are of the form

where is a nonterminal and

, ...,

are strings formed of symbols in and (finite sets of terminal and nonterminal symbols respectively).

Informally, such a rule asserts that

every string over

that satisfies each of the syntactical conditions represented

by , ...,

therefore satisfies the condition defined by .

Formal definition

A conjunctive grammar is defined by the 4-tuple where

{{mvar|V}} is a finite set; each element is called a nonterminal symbol or a variable. Each variable represents a different type of phrase or clause in the sentence. Variables are also sometimes called syntactic categories.
{{math|Σ}} is a finite set of terminals, disjoint from {{mvar|V}}, which make up the actual content of the sentence. The set of terminals is the alphabet of the language defined by the grammar {{mvar|G}}.
{{mvar|R}} is a finite set of productions. The members of {{mvar|R}} are called the rules or productions of the grammar.
{{mvar|S}} is the start variable (or start symbol), used to represent the whole sentence (or program). It must be an element of {{mvar|V}}.

It is common to list all right-hand sides for the same left-hand side on the same line, using | (the pipe symbol) to separate them. Rules and can hence be written as .

Two equivalent formal definitions

of the language specified by a conjunctive grammar exist.

One definition is based upon representing the grammar

as a system of language equations with union, intersection and concatenation

and considering its least solution.

The other definition generalizes

Chomsky's generative definition of the context-free grammars

using rewriting of terms over conjunction and concatenation.

Definition by derivation

For any strings , we say {{mvar|u}} directly yields {{mvar|v}}, written as , if

either there is a rule such that and ,
or there exists a string such that and .

For any string we say {{mvar|G}} generates {{mvar|w}}, written as if such that .

The language of a grammar is the set of {{clarify span|all strings|reason=Should be 'all strings from Sigma*' ?|date=June 2018}} it generates.

Example

The grammar , with productions

,

is conjunctive. A typical derivation is : This makes it clear that . The language is not context-free, proved by the pumping lemma.

Parsing algorithms

Though the expressive power of conjunctive grammars

is greater than those of context-free grammars,

conjunctive grammars retain some of the latter.

Most importantly, there are generalizations of the main context-free parsing algorithms,

including the linear-time recursive descent,

the cubic-time generalized LR,

the cubic-time Cocke-Kasami-Younger,

as well as Valiant's algorithm running as fast as matrix multiplication.

Theoretical properties

A number of theoretical properties of conjunctive grammars have been researched,

including the expressive power of grammars over a one-letter alphabet{{cn|date=June 2018}}

and {{clarify span|numerous undecidable problems|reason=Both the main decidable and the main undecidable properties should be stated, as well as the practical relevance of both.|date=June 2018}}.

This work provided a basis

for the study language equations of a more general form.

Synchronized alternating pushdown automata

Aizikowitz and Kaminski^[1] introduced a new class of pushdown automata (PDA) called synchronized alternating pushdown automata (SAPDA). They proved it to be equivalent to conjunctive grammars in the same way as nondeterministic PDAs are equivalent to context-free grammars.

References

1. ^{{cite book|last1=Aizikowitz|first1=Tamar|title=Computer Science – Theory and Applications|last2=Kaminski|first2=Michael|chapter=LR(0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata|volume=6651|year=2011|pages=345–358|issn=0302-9743|doi=10.1007/978-3-642-20712-9_27|series=Lecture Notes in Computer Science|isbn=978-3-642-20711-2}}

Alexander Okhotin, Conjunctive grammars. Journal of Automata, Languages and Combinatorics, 6:4 (2001), 519-535. (pdf)
Alexander Okhotin, [https://dx.doi.org/10.1016/j.cosrev.2013.06.001 Conjunctive and Boolean grammars: The true general case of the context-free grammars.] Computer Science Review, 9 (2013), 27-59.
Artur Jeż. Conjunctive grammars can generate non-regular unary languages. International Journal of Foundations of Computer Science 19(3): 597-615 (2008) Technical report version (pdf){{dead link|date=August 2017 |bot=InternetArchiveBot |fix-attempted=yes }}

External links

Artur Jeż. Conjunctive grammars can generate non-regular unary languages. Slides of talk held at the International Conference on Developments in Language Theory 2007.
Alexander Okhotin's page on conjunctive grammars.
Alexander Okhotin. [https://web.archive.org/web/20070929110312/http://www.tucs.fi/publications/insight.php?id=tOkhotin06a Nine open problems for conjunctive and Boolean grammars].

1 : Formal languages

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。