Skip to main content

Grammar in Automata | Types of Grammar

Grammar in Automata-

Formal Definition-

A Grammar is a 4-tuple such that
G = (V , T , P , S)
where-

  • V = Finite non-empty set of non-terminal symbols
  • T = Finite set of terminal symbols
  • P = Finite non-empty set of production rules
  • S = Start symbol

Grammar Constituents-

A Grammar is mainly composed of two basic elements-
1. Terminal symbols
2. Non-terminal symbols

1. Terminal Symbols-

  • Terminal symbols are those which are the constituents of the sentence generated using a grammar.
  • Terminal symbols are denoted by using small case letters such as a, b, c etc.

2. Non-Terminal Symbols-

  • Non-Terminal symbols are those which take part in the generation of the sentence but are not part of it.
  • Non-Terminal symbols are also called as auxiliary symbols or variables.
  • Non-Terminal symbols are denoted by using capital letters such as A, B, C etc.

Examples of Grammar-

Example-01:

Consider a grammar G = (V , T , P , S) where-
  • V = { S }                                                  // Set of Non-Terminal symbols
  • T = { a , b }                                              // Set of Terminal symbols
  • P = { S → aSbS , S → bSaS , S → ∈ }   // Set of production rules
  • S = { S }                                                   // Start symbol
This grammar generates the strings having equal number of a’s and b’s

Example-02:

Consider a grammar G = (V , T , P , S) where-

  • V = { S , A , B }                                                  // Set of Non-Terminal symbols
  • T = { a , b }                                                        // Set of Terminal symbols
  • P = { S → ABa , A → BB , B → ab , AA → b }  // Set of production rules
  • S = { S }                                                            // Start symbol

Types of Grammars-

Grammars are classified on different basis as:-
We will discuss all these types of grammar one by one in detail.

Equivalent Grammars-

Two grammars are said to be equivalent if they generate the same languages.

Example-

Consider the following two grammars-
Grammar G1-
S → aSb / ∈
Grammar G2-
S → aAb / ∈
A → aAb / ∈

Thus, L(G1) = L(G2)

Since both the grammars generate the same language, therefore they are equivalent.
∴ G1 ≡ G2


Comments

Post a Comment

Popular posts from this blog

Code Optimization | Code Optimization Techniques

Code Optimization- Code Optimization is an approach to enhance the performance of the code. The process of code optimization involves- Eliminating the unwanted code lines Rearranging the statements of the code Advantages- The optimized code has the following advantages- Optimized code has faster execution speed. Optimized code utilizes the memory efficiently. Optimized code gives better performance. Code Optimization Techniques- Important code optimization techniques are- Compile Time Evaluation Common sub-expression elimination Dead Code Elimination Code Movement Strength Reduction 1. Compile Time Evaluation- Two techniques that falls under compile time evaluation are- A) Constant Folding- In this technique, As the name suggests, it involves folding the constants. The expressions that contain the operands having constant values at compile time are evaluated. Those express...
Post a Comment
Read more

Three Address Code | Examples

Three Address Code- Three Address Code is a form of an intermediate code. The characteristics of Three Address instructions are- They are generated by the compiler for implementing Code Optimization . They use maximum three addresses to represent any statement. They are implemented as a record with the address fields. General Form- In general, Three Address instructions are represented as- a = b op c Here, a, b and c are the operands. Operands may be constants, names, or compiler generated temporaries. op represents the operator. Examples- Examples of Three Address instructions are- a = b + c c = a x b Common Three Address Instruction Forms- The common forms of Three Address instructions are- 1. Assignment Statement- x = y op z and x = op y Here, x, y and z are the operands. op represents the operator. It assigns the result obtained after solving the right side expression of the a...
Post a Comment
Read more

Eliminating Left Recursion

1. Left Recursion- A production of grammar is said to have left recursion if the leftmost variable of its RHS is same as variable of its LHS. A grammar containing a production having left recursion is called as Left Recursive Grammar. Example- S → Sa / ∈ ( Left Recursive Grammar ) Elimination of Left Recursion Left recursion is eliminated by converting the grammar into a right recursive grammar. If we have the left-recursive pair of productions- A  → Aα / β (Left Recursive Grammar) where β does not begin with an A. Then, we can eliminate left recursion by replacing the pair of productions with- A  →  βA’ A’  →  αA’ / ∈ (Right Recursive Grammar) This right recursive grammar functions same as left recursive grammar. PRACTICE PROBLEMS BASED ON LEFT RECURSION ELIMINATION- Problem-01: Consider the following grammar and eliminate left recursion- A → ABd / Aa / a...
Post a Comment
Read more