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...

Elimination of Left Factoring

In left factoring, We make one production for each common prefixes. The common prefix may be a terminal or a non-terminal or a combination of both. Rest of the derivation is added by new productions. The grammar obtained after the process of left factoring is called as Left Factored Grammar . Example-   PRACTICE PROBLEMS BASED ON LEFT FACTORING- Problem-01: Do left factoring in the following grammar- S → iEtS / iEtSeS / a E → b Solution- The left factored grammar is- S → iEtSS’ / a S’ → eS / ∈ E → b Problem-02: Do left factoring in the following grammar- A → aAB / aBc / aAc Solution- Step-01: A → aA’ A’ → AB / Bc / Ac Again, this is a grammar with common prefixes. Step-02: A → aA’ A’ → AD / Bc D → B / c This is a left factored grammar. Problem-03: Do left factoring in the following grammar- S → bSSaaS / bSSaSb / bSb / a Solution- ...

Testing a Program – An Example

Question: Write a set of test cases – specific set of data – to properly test a relatively Simple program. Create a set of test data for the program - data the program must handle correctly to be considered a successful program. Here’s a description of the program: “The program reads three integer values from an input dialog. The three values represent the lengths of the sides of a triangle. The program displays a message that states whether the triangle is scalene, isosceles, or equilateral”. Code: The function triangle takes three integer parameters that are interpreted as the lengths of the sides of a triangle. It returns whether the triangle is equilateral (three lengths equal), isosceles (two lengths equal), scalene (no lengths equal), or invalid (impossible lengths). Evaluate your test cases: Evaluate your set of test cases by using it to answer the following questions. Give yourself one point for each “YES” answer. Do you have a test case that represents a ...