Grammar in TOC

Grammar in TOC use the standard way of representing the language. A collection of string is known as language. Two method for check the particular string is the part of the language or not. First method is called an Automata and second method is  also known as Grammar. It is denoted by ‘G’ in TOC. A Grammar (G) is defined by using four quadruples.

These quadruples are as follows.

G = {V,T,P,S}

Where V, T, P, S are the elements of Grammar.

Hare the explanation of four quadruples are given.

• V show the Variables and Variables are known as Non-Terminals. It is denoted by ‘V’. It is used to put the values.
• T show the Terminals. It is denoted by ‘T’. It is used to terminate the string.
• P show the Production Rules. It is denoted by ‘P’. It is used to generate the language.
• S show the Start Symbol. It is denoted by ‘S’. Every production rule start with Start Symbol.

Real Life Examples of Grammar in TOC

Grammar is the same as the English Grammar. If the sentence is the grammatically correct it will be a part of the language and if the sentence is grammatically false it will not be a part of the language. The following real life example are as given.

• Here is your coffee. It is an valid example of Grammar in TOC.
• Is here coffee yours. It is an invalid example of Grammar in TOC.

Examples of Grammar in TOC

S → a S b / ε

Now, we solve this example step by step.

1.Empty String (ε)

Step 1: First apply the S → ε.

Final String: S → ε

2. String ab

Step 1: First apply the S → a S b.

String: S → aSb

Step 2: Second, put the value of S.

String: aSb → aεb

Step 3: Third, again put the value of S and remove the ε.

Final String: aεb →  ab

Note: ε means nothing, so we can removed it.

3. String aabb

Step 1: First apply the S → a S b.

String: S → aSb

Step 2: Second, put the value of S.

String: aSb → aaSbb

Step 3: Third, put the value of S.

String: aaSbb → aaεbb

Step 4: Fourth, again put the value of S.

Final String: aaεbb → aabb

Note: ε means nothing, so we can removed it.

4. String aaabbb

Step 1: First, apply the S → a S b.

String: S → aSb

Step 2: Second, Put the value of S.

String: aSb → aasbb

Step 3: Third, put the value of S.

String: aaSbb → aaaSbbb

Step 4: Fourth, again put the value of S.

String: aaaSbbb → aaaεbbb

Step 5: In last, put the value of S and remove the ε and we can get the final string.

Final String: aaaεbbb → aaabbb

Note: ε means nothing, so we can removed it.

We use the same method for next string aaaabbbb, aaaaaabbbbb, ….., aⁿ bⁿ.

Introduction To Chomsky Hierarchy

Noam Chomsky found the Chomsky Hierarchy in 1956. So it is also known as Chomsky Hierarchy. According to Noam Chomsky four types of Chomsky Hierarchy and these explanation also known as Chomsky Hierarchy.

Types of Grammar in Chomsky Hierarchy

 

Real Life Example of Chomsky Hierarchy

Explanation

In simple words we can explain the Chomsky Hierarchy in real life example. In this following example show that Lahore is in Pakistan, Pakistan is in Asia and Asia is on Earth. According to Noam Chomsky four types of Chomsky Hierarchy are as follow.

Types of Grammar

Hare four most important types of Grammar are as follow.

1.Type-0 Grammar/Recursive Enumerable Grammar (REG)/Unrestricted Grammar/Phase Structured Grammar

Type-0 Grammar is known as Recursive Enumerable Grammar (REG). Type-0 Grammar is used to generate Recursive Enumerable Language (REL) which is accepted by Turing Machine (TM). There are no restrictions on the rules of Type-0 Grammar.

REG → REL → TM

2.Type-1 Grammar/Context Sensitive Grammar (CSG)/Length Increasing Grammar/Non-Contracting Grammar

Type-1 Grammar is known as Context Sensitive Grammar (CSG). Type-1 Grammar is used to generate Context Sensitive Language (CSL) which is accepted by Linear Bounded Automata (LBA). There are restrictions on the rules of Type-1 Grammar.

CSG → CSL → LBA

3.Type-2 Grammar/Context Free Grammar (CFG)

Type-2 Grammar is known as Context Free Grammar (CFG). Type-2 Grammar is used to generate Context Free Language (CFL) which is accepted by Pushdown Automata (PDA). There are restrictions on the rules of Type-2 Grammar.

CFG → CFL → PDA

4.Type-3 Grammar/Regular Grammar (RG)

Type-3 Grammar is also known as Regular Grammar (RG). Type-3 Grammar is used to generate Regular Language (RL) which is accepted by Finite Automata (FA). There are strict restrictions on the rules of Type-3 Grammar.

RG → RL → FA