Grammars in Automata Theory

Grammar can defined as 4 tuples, it means G={N,T,S,P}  where,

• N- set of variables or non terminal symbol
• T- terminal symbol
• S- starting symbol, S ∊ N
• P- production rule for terminal or non-terminal (∝➝β)

Example

1. Grammar :-

            N ⇒ {S,A}

            T ⇒ {0,1}

            S ⇒ S

            P ⇒ { S➝A, A➝ 1A | 0A | 0 | 1 | ∊ }

       Derivation of sentences:-

            S  ➝ A

                ➝ 1A

                ➝ 11A

                ➝ 110A

                ➝ 1100

        We can derivate string "1100" as this way using above grammer.

Grammars can used to express languages. Noam chomsky illustrated chart for classified grammars. According to the 

chomsky-hierarchy (you can see chomsky-hierarchy😊) there are 4 types of grammar. 

Accordingly chomsky classification, we will learn about regular grammar (type-3 grammar) under the part of this section.

    What is the Linear Grammar ?    

In the Linear Grammars ,there is at most one variable at the right side of a production.

                        S ➝ uAV

                        S ➝ a

Example

    1. Is G1  Linear? No

            S ➝ aABb 

            A ➝ a | ∊

            B ➝  b | ∊ 

     2. Is G1  Linear? Yes 

            S ➝ A | bB   

            A ➝ bB | a | ∊  

            B ➝ Ab  

  

There are 2 types of linear grammars such as left and right linear grammar.

            left linear grammar :- 

                In left linear grammar, start from non-terminal characters all productions have form as A ➝ Bx

                            S ➝ a

                            S ➝ ∊ 

                            S ➝ Aa | Ab

            right linear grammar :- 

                In right linear grammar, end by non-terminal characters all   productions have form as A ➝ xB

                            S ➝ a

                            S ➝ ∊ 

                            S ➝ aA | bA