|
In computer science a formal grammar is a way to describe a formal language, i.e., a subset of strings over a certain finite alphabet. The basic idea behind these grammars is that we generate strings by beginning with a special start symbol and then apply rules that indicate how certain combinations of symbols may be replaced with other combinations of symbols. This is repeated until the result contains only symbols from the alphabet. The language of the grammar then consists of all the strings that can be generated that way. |
|
In computer science a formal grammar is a way to describe a formal language, i.e., a set of finite-length strings over a certain finite alphabet. The basic idea behind these grammars is that we generate strings by beginning with a special start symbol and then apply rules that indicate how certain combinations of symbols may be replaced with other combinations of symbols. This is repeated until the result contains only symbols from the alphabet. The language of the grammar then consists of all the strings that can be generated that way. |
|
: Something about Noam Chomsky and [transformational grammar]?s and [generative grammar]?s should be written here. |
|
One common classification system for grammars is the Chomsky hierarchy, a set of four types of grammars developed by Noam Chomsky in the 1950s. Every possible grammar is a member of at least one of these four classes. The most important result of that work was the proof that every language that can be accepted by a Turing machine can also be generated by some grammar, and vice versa. In this sense, grammars are universal. : Something about [transformational grammar]?s and [generative grammar]?s should be written here. |
|
The language of a formal grammar G = (N, Σ, P, S), denoted as L(G), is defined as all those strings over Σ that can be generated by starting with the start symbol S and then applying the production rules in P until no more no more nonterminal symbols are present. |
|
The language of a formal grammar G = (N, Σ, P, S), denoted as L(G), is defined as all those strings over Σ that can be generated by starting with the start symbol S and then applying the production rules in P until no more nonterminal symbols are present. |
|
and the nonterminal symbol S as the start symbol. Some examples of the derivation of strings in L(G) are: (The used production rules are indicated in brackets.) * S -> (2) abc * S -> (1) aBSc -> (2) aBabcc -> (4) aaBbcc -> (5) aabbcc * S -> (1) aBSc -> (1) aBaBScc? -> (2) aBaBabccc? -> (4) aaBBabccc -> (4) aaBaBbccc? -> (4) aaaBBbccc -> (5) aaaBbbccc -> (5) aaabbbccc See also: [transformational grammar]? -- [generative grammar]? -- Chomsky hierarchy -- regular grammar -- context-sensitive grammar -- context-free grammar -- regular grammar |
|
and the nonterminal symbol S as the start symbol. Some examples of the derivation of strings in L(G) are: (The used production rules are indicated in brackets and replaced part is each time indicated in bold.) * S -> (2) abc * S -> (1) aBSc -> (2) aBabcc -> (4) aaBbcc -> (5) aabbcc * S -> (1) aBSc -> (1) aBaB?Scc -> (2) aBaBabccc -> (4) aaBBabccc -> (4) aaBaBbccc -> (4) aaaBBbccc -> (5) aaaBbbccc -> (5) aaabbbccc It will be clear that this grammar defines the language { anbncn | n > 1 } where an denotes a string of n a's. See also: [transformational grammar]? -- [generative grammar]? -- Chomsky hierarchy -- regular grammar -- context-sensitive grammar -- context-free grammar /Talk? |
![[Home]](wikipedia.png)