Context-Free Grammars:

A context-free grammar basically consists of a finite set of grammar rules. To define grammar rules, we suppose that we have two kinds of symbols: the terminals, which are the symbols of the alphabet underlying languages under consideration, and nonterminals, which act like variables ranging over strings of terminals. A rule is of the form A → α, where A is a single nonterminal, and the right-hand side α is a string of terminal and nonterminal symbols.  As usual, first we are required to define what the object is (a context-free grammar), and then we are required to explain how it is used. Unlike automata, grammars are used to create strings, rather than recognize them.

Definition: A context-free grammar is a quadruple G = (V, Σ, P, S), where

• V is a finite set of symbols known as vocabulary (or set of grammar symbols);

• Σ ⊆ V is the set of terminal symbols (for the short, terminals);

• S ∈ (V - Σ) is a designated symbol known as start symbol;

• P ⊆ (V - Σ) × V* is a finite set of productions (or rewrite rules,).

The set N = V - Σ is known as set of nonterminal symbols (for short, nonterminals).  Therefore, P ⊆ N × V*, and every production A, α is denoted as A → α.  A production of the form A →   is known as epsilon rule.

Remark :   Context-free  grammars  are defined  as G  = (V_N , V_T , P, S). The correspondence with definition is that Σ = V_T  and N = V_N , so that V = V_N ∪ V_T . Therefore, in this other definition, it is essential to assume that V_T  ∩ V_N  = ∅.

Example 1: G₁  = ({E, a, b}, {a, b}, P, E), where P is the set of rules

E -→ aEb,

E -→ ab.

This grammar generates the language L₁= {aⁿbⁿ| n ≥ 1}, which is not regular.

Example 2: G₂ = ({E, +, ∗, (, ), a}, {+, ∗, (, ), a}, P, E), here P is the set of rules

E -→ E + E,

E -→ E ∗ E,

E -→ (E),

E -→ a.

This grammar generates the set of arithmetic  expressions.

Email based Automata assignment help - homework help

The study of automata is an important area of theory of computation. Students feel trouble in solving automata questions. We at www.expertsmind.com offers Automata assignment help - Automata homework help and online tutoring with best qualified and experienced computer science tutor's help. We cover all topics including Context-free grammars and languages in assignment help - homework help service. Get solved problems in automata theory with step by step answers anytime from expert tutors at expertsmind.