Generalized context-free grammar

Generalized Context-free Grammar (GCFG) is a grammar formalism that expands on context-free grammars by adding potentially non-context free composition functions to rewrite rules. Head grammar (and its weak equivalents) is an instance of such a GCFG which is known to be especially adept at handling a wide variety of non-CF properties of natural language.

Description

A GCFG consists of two components: a set of composition functions that combine string tuples, and a set of rewrite rules. The composition functions all have the form $f(\langle x_{1},...,x_{m}\rangle ,\langle y_{1},...,y_{n}\rangle ,...)=\gamma$, where $\gamma$ is either a single string tuple, or some use of a (potentially different) composition function which reduces to a string tuple. Rewrite rules look like $X\to f(Y,Z,...)$, where $Y$, $Z$, ... are string tuples or non-terminal symbols.

The rewrite semantics of GCFGs is fairly straight forward. An occurrence of a non-terminal symbol is rewritten using rewrite rules as in a context-free grammar, eventually yielding just compositions (composition functions applied to string tuples or other compositions). The composition functions are then applied, reducing successively reducing the tuples to a single tuple.

Example

A simple translation of a context-free grammar into a GCFG can be performed in the following fashion. Given the grammar in (1), which generates the palindrome language $\{ww^{R}:w\in \{a,b\}^{*}\}$, where $w^{R}$ is the string reverse of $w$, we can define the composition function conc as in (2a) and the rewrite rules as in (2b).

1. $S\to \epsilon ~|~aSa~|~bSb$
2. 1. $conc(\langle x\rangle ,\langle y\rangle ,\langle z\rangle )=\langle xyz\rangle$
   2. $S\to conc(\langle \epsilon \rangle ,\langle \epsilon \rangle ,\langle \epsilon \rangle )~|~conc(\langle a\rangle ,S,\langle a\rangle )~|~conc(\langle b\rangle ,S,\langle b\rangle )$

The CF production of abbbba is

S

aSa

abSba

abbSbba

abbbba

and the corresponding GCFG production is

$S\to conc(\langle a\rangle ,S,\langle a\rangle )$

$conc(\langle a\rangle ,conc(\langle b\rangle ,S,\langle b\rangle ),\langle a\rangle )$

$conc(\langle a\rangle ,conc(\langle b\rangle ,conc(\langle b\rangle ,S,\langle b\rangle ),\langle b\rangle ),\langle a\rangle )$

$conc(\langle a\rangle ,conc(\langle b\rangle ,conc(\langle b\rangle ,conc(\langle \epsilon \rangle ,\langle \epsilon \rangle ,\langle \epsilon \rangle ),\langle b\rangle ),\langle b\rangle ),\langle a\rangle )$

$conc(\langle a\rangle ,conc(\langle b\rangle ,conc(\langle b\rangle ,\langle \epsilon \rangle ,\langle b\rangle ),\langle b\rangle ),\langle a\rangle )$

$conc(\langle a\rangle ,conc(\langle b\rangle ,\langle bb\rangle ,\langle b\rangle ),\langle a\rangle )$

$conc(\langle a\rangle ,\langle bbbb\rangle ,\langle a\rangle )$

$\langle abbbba\rangle$

Linear Context-free Rewriting Systems (LCFRSs)

Weir (1988) describes two properties of composition functions, linearity and regularity. A function defined as $f(x_{1},...,x_{n})=...$ is linear if and only if each variable appears at most once on either side of the =, making $f(x)=g(x,y)$ liner but not $f(x)=g(x,x)$. A function defined as $f(x_{1},...,x_{n})=...$ is regular if the left hand side and right hand side have the exact same variables, making $f(x,y)=g(y,x)$ regular but not $f(x)=g(x,y)$ or $f(x,y)=g(x)$.

A grammar in which all composition functions are both linear and regular is called a Linear Context-free Rewriting System (LCFRS), a subset of the GCFGs with strictly less computational power than the GCFGs as a whole, which is weakly equivalent to multicomponent Tree adjoining grammars. Head grammar is an example of an LCFRS that is strictly less powerful than the class of LCFRSs as a whole.

Converting a context-free grammar to Greibach Normal Form and Chomsky normal form using CNF/GNF software

CNF / GNF : is a software make the automatic Convertion of a context-free grammar to:

1- Chomsky normal form grammar (CNF).

2- Greibach normal form grammar (GNF).

and also it show you the new grammar in each of the steps of the transformation.

A- Chomsky normal normal grammar (CNF)

1- reduced grammar.

2- epsilon-free grammar.

3- grammar without cycles and unit rules .

4-CNF.

B-Greibach normal form grammar (GNF).

1- reduced grammar.

2- epsilon-free grammar.

3- without cycles and unit rules.

4- non-left recursive grammar.

5- GNF.

with this application you can have CNF and GNF for any context-free grammar just in few steps.

just run the application and create new project and enter your grammar and click done and you will have :

CNF and GNF grammar and the new grammar in each of the steps of the transformation.

See also

• CNF/GNF
• Chomsky normal form software
• CNF/GNF Homepage
• CNF/GNF download