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

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

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

Mindspark

Search This Blog