PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (190)
Orphanage
Unclass'd (1)
Unproven (496)
Corrections (7)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: Very high
formal grammar (Definition)

Introduction

A grammar, loosely speaking, is a set of rules that can be applied to words to generate sentences in a language. For example, with the grammar of the English language, one can form syntactically correct sentences such as “The elephant drove his bicycle to the moon,” regardless whether the sentence is meaningful or not.

The mathematical abstraction of a grammar is known as a formal grammar. Instead of generating sentences from words, a formal grammar generates words from symbols and other words. The following basic ingredients are necessary in a formal grammar:

  • a collection of symbols called an alphabet,
  • a collection of rules, called rewriting rules, specifying how one can generate new words from existing ones, and
  • a collection of initial words that serve to initialize the generation of new words.
To see how these rewriting rules work, let us look at an example. Let $ \lbrace a,b\rbrace$ be the alphabet as well as the set of initial words. With the rewriting rules given by: from a word $ x$ we can form the word $ ax$, as well as the word $ xa$, we would be able to generate words like
$\displaystyle aa, \quad aaa, \quad ab, \quad baa$
However, words such as
$\displaystyle bb, \quad baba, \quad baaab$
can not be produced.

Note that by adding an extra symbol $ \sigma$ to the above alphabet, and two additional rewriting rules given by “from $ \sigma$ form $ a$” and “from $ \sigma$ form $ b$”, it is not hard to see that any word that can be generated by the first grammar can be generated by this new grammar.

Definition

Formalizing what we have discussed above, we say that a formal grammar $ G$ is a quadruple $ (\Sigma,N,P,\sigma)$, where

  1. $ (\Sigma,P)$ is a rewriting system;
  2. $ N$ is a subset of $ \Sigma$ whose elements are called non-terminals, and $ T:=\Sigma-N$ the set of terminals;
  3. an element $ \sigma\in N$ called the starting symbol.
Instead of writing $ G=(\Sigma,N,P,\sigma)$, the quadruple $ (T,N,P,\sigma)$ is another way of representing $ G$ (as long as the conditions $ \Sigma=T\cup N$ and $ T\cap N=\varnothing$ are satisfied).

A formal grammar is variously known as a phrase-structure grammar, an unrestricted grammar, or simply a grammar. A formal grammar is sometimes also called a rewriting system in the literature, although the two notions are distinct on PlanetMath.

Given a formal grammar $ G$, the formal language generated by $ G$ is the set

$\displaystyle L(G):=\lbrace w\in T^*\mid \sigma \stackrel{*}{\Rightarrow}w\rbrace,$
where $ \stackrel{*}{\Rightarrow}$ is the derivability relation in the rewriting system $ (\Sigma,P)$. A formal language is also known as a phrase-structure language.

A language $ L$ over an alphabet $ A$ is said to be generable by a formal grammar if there is a formal grammar $ G$ such that $ L=L(G)\cap A^*$.

Example. Continuing from the example in the previous section, we can put $ T=\lbrace a,b\rbrace$ and $ N=\lbrace \sigma\rbrace$. For the set $ P$ of productions, we have four

  1. $ \sigma \to \sigma a$
  2. $ \sigma \to a\sigma$
  3. $ \sigma \to a$
  4. $ \sigma \to b$
Then $ G=(\Sigma,N,P,\sigma)$ is a formal grammar. It is not hard to see that $ \sigma \stackrel{*}{\Rightarrow}baa$, as $ \sigma \to \sigma a \to \sigma aa \to baa$. In fact, $ L(G)$ consists of all words such that $ a$ occurs at least once and $ b$ occurs at most once.

Remarks.

  • Not every language can be generated by a formal grammar. Given a finite alphabet $ \Sigma$, $ \Sigma^*$ is countably infinite, and therefore there are uncountably many languages over $ \Sigma$. However, there are only a countably infinitely many languages that can be generated by formal grammars.
  • Every language generated by a formal grammar is recursively enumerable.
  • Every context-sensitive grammar is equivalent to a formal grammar, and under the Chomsky hierarchy, the class of formal languages is of class 0.

Bibliography

1
H.R. Lewis, C.H. Papadimitriou Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs, New Jersey (1981).



"formal grammar" is owned by CWoo. [ full author list (2) | owner history (2) ]
(view preamble)

View style:

See Also: semi-Thue system, language, Post system

Other names:  phrase-structure grammar, unrestricted grammar, grammar, phrase-structure language, terminal symbol, non-terminal symbol, initial-symbol, initial symbol, start symbol
Also defines:  formal language, terminal, non-terminal, starting symbol, production, generable by a formal grammar

Attachments:
context-free language (Definition) by CWoo
context-sensitive language (Definition) by CWoo
equivalent grammars (Definition) by CWoo
Log in to rate this entry.
(view current ratings)

Cross-references: class, Chomsky hierarchy, context-sensitive grammar, recursively enumerable, countably infinite, finite, section, relation, PlanetMath, subset, rewriting system, generated by, alphabet, collection, necessary, generating, language, sentences, generate
There are 36 references to this entry.

This is version 27 of formal grammar, born on 2006-12-09, modified 2008-07-18.
Object id is 8609, canonical name is FormalGrammar.
Accessed 4510 times total.

Classification:
AMS MSC: 03D05 (Mathematical logic and foundations :: Computability and recursion theory :: Automata and formal grammars in connection with logical questions)
 68Q45 (Computer science :: Theory of computing :: Formal languages and automata)
 68Q42 (Computer science :: Theory of computing :: Grammars and rewriting systems)
 91F20 (Game theory, economics, social and behavioral sciences :: Other social and behavioral sciences :: Linguistics)
Pending Errata and Addenda
None.
[ View all 2 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)