Unit 3-linear grammar PDF

Preview

Summary

It consist of notes of theory of computation for linear grammar...

Description

Linear grammar In computer science, a linear grammar is a context-free grammar that has at most one nonterminal (Variables) in the right hand side of each of its productions. A linear language is a language generated by some linear grammar. • A linear grammar is a context-free grammar that has at most one nonterminal symbol on the right hand side of each grammar rule. Here is a linear grammar: S → aA A → aBb B → Bb Example A simple linear grammar is G with N = {S}, Σ = {a, b}, P with start symbol S and rules S → aSb S→ε It generates the language

.

Relationship with regular grammars Two types of linear grammars are given in the following: 1) Left Linear or Left regular grammars : The left-linear or left regular grammars, in which all nonterminals in right hand sides are at the left ends; e.g S → Aa A → ab 2) Right Linear or Right regular grammars : The right-linear or right regular grammars, in which all nonterminals in right hand sides are at the right ends.

e.g S → abaA A→ ε These two special types of linear grammars are known as the regular grammars; both can describe exactly the regular languages. Another special type of linear grammar is the following: linear grammars in which all nonterminals in right hand sides are at the left or right ends, but not necessarily all at the same end. By inserting new nonterminals, every linear grammar can be brought into this form without affecting the language generated. For instance, the rules of G above can be replaced with S → aA A → Sba S→ε Hence, linear grammars of this special form can generate all linear language.

Regular grammar and finite automata, 1) Conversion of Finite Automata to Right Linear Regular Grammar Converting finite automata to right linear grammar is very simple See below steps and example followed by it, we will understand the process. 1. Repeat the process for every state 2. Begin the process from start state 3. Write the production as the output followed by the state on which the transition is going 4. And at the last add ε because that's is required to end the derivation Note: We have added ε because either you could continue the derivation or would like to stop it. So to stop the derivation we have written ε

So we will apply the above procedure Pick start state and output is on symbol 'a' we are going on state B So we will write as : A -> aB And then we will pick state B and then we will go for each output. so we will get the below production. B -> aB/bB/ε So final we got right linear grammar as: A -> aB B -> aB/bB/ε

2) Conversion of Finite Automata to Left Linear Grammar Converting finite automata to left lienar grammar is somewhat tricky. See below steps and example followed by it, we will understand the process. 1. Take reverse of the finite automata 2. Then write right linear grammar following the previous lesson 3. Then take reverse of the right linear grammar 4. Take the step 2 output and we will write down "right linear grammar" for it. Begin from start state, that is B So,

B -> aB/bB/aA A -> ε And now reverse the right linear grammar to get the ouput = left linear Grammar B -> Ba/Bb/Aa A -> ε

FormulaFA -> Reverse of FA -> Right Linear Grammar -> Reverse of Right Linear Grammar = Left Linear Grammar 3) Conversion of Right Linear Grammar to Finite Automata Converting right linear grammar to Finite Automata is simple. Follow the steps: 1. Start from the first production 2. And then for every left alphabet go to SYMBOL followed by it 3. Start State: It will be the first production's state 4. Final State: Take those states which end up with input alphabets. eg. State A and C are below CFG. Here we are giving one right linear grammar A -> aB/bA/b B -> aC/bB C -> aA/bC/a

4) Conversion of Left Linear Grammar to Finite Automata Converting left linear grammar to Finite Automata is simple. Follow the steps: 1. Take reverse of CFG 2. Create Finite automata using previous example 3. Then again take reverse of the FA and that will be our final output 4. Start State: It will be the first production's state 5. Final State: Take those states which end up with input alphabets. eg. State A and C are below CFG Here we are giving one right linear grammar A -> Ba/Ab/b B -> Ca/Bb C -> Aa/Cb We will follow the steps 1. Take the reverse of the CFG A -> aB/bA/b B -> aC/bB C -> aA/bC/a 2. Now create the FA

Note: Only state A is final state in this example 3. Now take reverse of the above FA (this is final output)

Note: Here state A was itself a final state that is why it again become start state as well as final state....