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

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