Literal movement grammar

In linguistics and theoretical computer science, literal movement grammars (LMGs) are a grammar formalism intended to characterize certain extraposition phenomena of natural language such as topicalization and cross-serial dependency. LMGs extend the class of context free grammars (CFGs) by adding introducing pattern-matched function-like rewrite semantics, as well as the operations of variable binding and slash deletion. LMGs were introduced by A.V. Groenink in 1995.[1]

## Contents

* 1 Description
* 2 Example
* 3 Computational power
* 4 References

## Description

The basic rewrite operation of an LMG is very similar to that of a CFG, with the addition of arguments to the non-terminal symbols. Where a context-free rewrite rule obeys the general schema S->α for some non-terminal S and some string of terminals and/or non-terminals α, an LMG rewrite rule obeys the general schema X(x1,...,xn)->α, where X is a non-terminal with arity n (called a predicate in LMG terminology), and α is a string of "items", as defined below. The arguments xi are strings of terminal symbols and/or variable symbols defining an argument pattern. In the case where an argument pattern has multiple adjacent variable symbols, the argument pattern will match any and all partitions of the actual value that unify. Thus, if the predicate is f(xy) and the actual pattern is f(ab), there are three valid matches: x=ϵ, y=ab; x=a, y=b; x=ab, y=ϵ. In this way, a single rule is actually a family of alternatives.

An "item" in a literal movement grammar is one of

* f(x1,…,xn), a predicate of arity n,
* x:f(x1,…,xn), a variable binding x to the string produced by f(x1,...,xn), or
* f(x1,…,xn)/α, a slash deletion of f(x1,...,xn) by the string of terminals and/or variables α.

In a rule like f(x1,...,xm)->α y:g(z1,...zn) β, the variable y is bound to whatever terminal string the g predicate produces, and in α and β, all occurrences of y are replaced by that string, and α and β are produced as if terminal string had always been there.

An item x/y, where x is something that produces a terminal string (either a terminal string itself or some predicate), and y is a string of terminals and/or variables, is rewritten as the empty string (ϵ) if and only if g(y1,...,yn)=z, and otherwise cannot be rewritten at all.

## Example

LMGs can characterize the non-CF language {anbncn:n≥1} as follows:

S()->x:A() B(x)
A()->a A()
A()->ϵ
B(xy)->a/x b B(y)c
B(ϵ)->ϵ

The derivation for aabbcc, using parentheses also for grouping, is therefore

S()->x:A() B(x)->x:(a A()) B(x)->x:(aa A()) B(x)->x:aa B(x)->aa B(aa)

->aa a/a b B(a) c->aab B(a) c->aab a/a b B() cc->aabb B() cc ->aabbcc

## Computational power

Languages generated by LMGs contain the context-free languages as a proper subset, as every CFG is an LMG where all predicates have arity 0 and no production rule contains variable bindings or slash deletions.

## References

1. ↑ Groenink, Annius V. 1995. Literal Movement Grammars. In Proceedings of the 7th EACL Conference.

* v
* t
* e

Automata theory: formal languages and formal grammars

| Chomsky hierarchy| Grammars| Languages| Abstract machines

|
|
|

* Type-0
* —
* Type-1
* —
* —
* —
* —
* —
* Type-2
* —
* —
* Type-3
* —
* —

* Unrestricted
* (no common name)
* Context-sensitive
* Positive range concatenation
* Indexed
* —
* Linear context-free rewriting systems
* Tree-adjoining
* Context-free
* Deterministic context-free
* Visibly pushdown
* Regular
* —
* Non-recursive

* Recursively enumerable
* Decidable
* Context-sensitive
* Positive range concatenation*
* Indexed*
* —
* Linear context-free rewriting language
* Tree-adjoining
* Context-free
* Deterministic context-free
* Visibly pushdown
* Regular
* Star-free
* Finite

* Turing machine
* Decider
* Linear-bounded
* PTIME Turing Machine
* Nested stack
* Thread automaton
* restricted Tree stack automaton
* Embedded pushdown
* Nondeterministic pushdown
* Deterministic pushdown
* Visibly pushdown
* Finite
* Counter-free (with aperiodic finite monoid)
* Acyclic finite

Each category of languages, except those marked by a *, is a proper subset of the category directly above it. Any language in each category is generated by a grammar and by an automaton in the category in the same line.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Literal movement grammar. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Literal_movement_grammar&oldid=287811"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template