Introduction

As part of our Formal Languages and Automata Theory, in this blog, we will be heading up for something that we haven't discussed so far. If you have noticed in the previous blog, we discussed that a Finite Automata is something that accepts Regular Language. We didn't discussed much about that in the previous blog but, now we are going to.

Now, we have a basic idea of Chomsky hierarchy of languages. Let's just recall the hierarchy of languages

Grammar

Let's first get habituated with the word 'Grammar'. We all know that grammar means the rules of a language. We all know that every language have grammar. Just like that every language that gets accepted by any automaton also has its own set of rules to construct the language which is grammar.

Let's define grammar formally. Let G be a grammar then it is defined as,

G = ( N, T, P, S )

where,

1. N is the set of non-terminals

2. T is the set of Terminals

3. P is the set of production rules

4. S is the start symbol of the production

Now, you all must be wondering what are N, T, P and S. Let's get to know about these in the following example:

S -> aSa|A

A -> a|ε

The above are the productions of the language. Which is the production set. Productions are what define language. Let's first keep it that way and know about other things. You can see S and A are the Non-Terminals. the symbol a is a terminal. Whenever we derive some set of strings, we will be starting from one Non-terminal which is, in this case 'S'.

Let's derive a few strings from this grammar:

As we know we should start from start symbol, we start from the symbol S

S -> aSa

S -> aaSaa

S -> aaAaa

S -> aaεaa

S -> aaaa

This grammar generates the language, that accepts the strings a^n where n > 1. This is how we derive a Language from a given grammar.

According to Noam Chomsky, we have 4 types of grammar:

1. Regular Grammar

2. Context Free Grammar

3. Context Sensitive Grammar

4. Recursively Enumerable Grammar

In detail discussion of these different kind of grammars is a topic of another day.

That's up for today, If you have came to this far, like and share is very much appreciable and subscribe to the news letter to never miss any of the blog posts.

Thank you...