Kellye Wright-Haynes

CMPS 300

Dr. Kokoly

Context-Free Grammars

A context-free grammar (CFG) is a set of recursive rewriting rules (or productions) used to generate patterns of strings.
A CFG consists of the following components: • a set of terminal symbols, which are the characters of the alphabet that appear in the strings generated by the grammar. • a set of nonterminal symbols, which are placeholders for patterns of terminal symbols that can be generated by the nonterminal symbols. • a set of productions, which are rules for replacing (or rewriting) nonterminal symbols (on the left side of the production) in a string with other nonterminal or terminal symbols (on the right side of the production). • a start symbol, which is a special nonterminal symbol that appears in the initial string generated by the grammar.
To generate a string of terminal symbols from a CFG, we: • Begin with a string consisting of the start symbol; • Apply one of the productions with the start symbol on the left hand size, replacing the start symbol with the right hand side of the production; • Repeat the process of selecting nonterminal symbols in the string, and replacing them with the right hand side of some corresponding production, until all nonterminals have been replaced by terminal symbols.

Regular Grammar
The regular grammars describe exactly all regular languages and are in that sense equivalent to finite state automata and regular expressions. Moreover, the right regular grammars by themselves are also equivalent to the regular languages, as are the left regular grammars.
Every regular grammar is a context-free grammar.
Every context-free grammar can be easily rewritten into a form in which only a combination of left regular and right regular rules is used. Therefore, such grammars can express all context-free languages. Regular grammars, which use either left-regular or right-regular rules but not both, can only express a smaller set of languages, called the regular languages. In that sense they are equivalent with finite state automata and regular expressions. (for illustration: the paradigmatic context-free language with strings of the form aibi is generated by the grammar G with N = {S, A}, Σ = {a, b}, P with the rules S → aA A → Sb S → ε and S being the start symbol. Note that this grammar has both left-regular and right-regular rules and is therefore not regular any more.)
Some textbooks and articles disallow empty production rules, and assume that the empty string is not present in languages.

CFGs vs Regular Expressions

Context-free grammars are strictly more powerful than regular expressions. • Any language that can be generated using regular expressions can be generated by a context-free grammar. • There are languages that can be generated by a context-free grammar that cannot be generated by any regular expression.
As a corollary, CFGs are strictly more powerful than DFAs and NDFAs.
The proof is in two parts: • Given a regular expression R , we can generate a CFG G such that L(R) == L(G). • We can define a grammar G for which there there is no FA F such that L(F) == L(G).