Converting Left Linear Grammar to Right Linear Grammar
How to convert a left linear
grammar to a right linear grammar
Roger L. Costello
May 28, 2014
Objective
This mini-tutorial will answer these questions:
1.
What is a linear grammar? What is a left linear
grammar? What is a right linear grammar?
2
Objective
This mini-tutorial will answer these questions:
1.
What is a linear grammar? What is a left linear
grammar? What is a right linear grammar?
2.
Left linear grammars are evil – why?
3
Objective
This mini-tutorial will answer these questions:
1.
What is a linear grammar? What is a left linear
grammar? What is a right linear grammar?
2.
Left linear grammars are evil – why?
3.
What algorithm can be used to convert a left
linear grammar to a right linear grammar?
4
Linear grammar
•
A
linear grammar
is a context-free grammar
that has at most one non-terminal symbol on
the right hand side of each grammar rule.
–
A rule may have just terminal symbols on the right
hand side (zero non-terminals).
•
Here is a linear grammar:
5
S
→ a
A
A → aBb
B → Bb
Left linear grammar
•
A
left linear grammar
is a linear grammar in
which the non-terminal symbol always occurs
on the left side.
•
Here is a left linear grammar:
S
→
Aa
A → ab
6
Right linear grammar
•
A
right linear grammar
is a linear grammar in
which the non-terminal symbol always occurs
on the right side.
•
Here is a right linear grammar:
S
→
abaA
A →
ε
7
Left linear grammars are evil
•
Consider this rule from a left linear grammar:
A → Babc
•
Can that rule be used to recognize this string:
abbabc
•
We need to check the rule for
B
:
B → Cb | D
•
Now we need to check the rules for
C
and
D
.
•
This is very complicated.
•
Left linear grammars require complex parsers.
8
Right linear grammars are good
•
Consider this rule from a right linear grammar:
A → abcB
•
Can that rule be used to recognize this string:
abcabb
•
We immediately see that the first part of the
string –
abc
– matches the first part of the rule.
Thus, the problem simplifies to this: can the rule
for
B
be used to recognize this string :
abb
•
Parsers for right linear grammars are much
simpler.
9
Convert left linear to right linear
Now we will see an algorithm for converting any
left linear grammar to its equivalent right linear
grammar.
S
→
Aa
A → ab
left linear
Both grammars generate this language: {aba}S
→
abaA
A →
ε
right linear
10
May need to make a new start symbol
The algorithm on the following slides assume
that the left linear grammar doesn’t have any
rules with the start symbol on the right hand
side.
–
If the left linear grammar has a rule with the start
symbol
S
on the right hand side, simply add this
rule:
S
0
→ S
11
Symbols used by the algorithm
•
Let
S
denote the start symbol
•
Let
A
,
B
denote non-terminal symbols
•
Let
p
denote zero or more terminal symbols
•
Let
ε
denote the empty symbol
12
Algorithm
1)
If the left linear grammar has a rule
S
→
p
, then
make that a rule in the right linear grammar
2)
If the left linear grammar has a rule
A
→
p
, then add
the following rule to the right linear grammar:
S
→
pA
3)
If the left linear grammar has a rule
B
→
Ap
, add the
following rule to the right linear grammar:
A
→
pB
4)
If the left linear grammar has a rule
S
→
Ap
, then
add the following rule to the right linear grammar:
A
→
p
13
Convert this left linear grammar
14
S
→
Aa
A → ab
left linear
Right hand side has terminals
15
S
→
Aa
A → ab
left linear
2) If the left linear grammar has this rule
A
→
p
,
then add the following rule to the right linear
grammar:
S
→
pA
S
→
abA
right linear
Right hand side of S has non-terminal
16
S
→
Aa
A → ab
left linear
4) If the left linear grammar has
S
→
Ap
, then
add the following rule to the right linear
grammar:
A
→
p
S
→
abA
A →
a
right linear
Equivalent!
17
S
→
Aa
A → ab
left linear
Both grammars generate this language: {aba}S
→
abA
A →
a
right linear
Convert this left linear grammar
18
left linear
S
0
→
S
S
→
A
b
S →
Sb
A → A
a
A →
a
S
→
A
b
S →
Sb
A → A
a
A →
a
original grammar
make a new
start symbol
Convert this
Right hand side has terminals
19
S
0
→
S
S
→
A
b
S →
Sb
A → A
a
A →
a
left linear
S
0
→
aA
right linear
2) If the left linear grammar has this rule
A
→
p
,
then add the following rule to the right linear
grammar:
S
→
pA
Right hand side has non-terminal
20
S
0
→
S
S
→
A
b
S →
Sb
A → A
a
A →
a
left linear
S
0
→
aA
A
→ bS
A → aA
S
→ bS
right linear
3) If the left linear grammar has a rule
B
→
Ap
, add the
following rule to the right linear grammar:
A
→
pB
Right hand side of start symbol has
non-terminal
21
S
0
→
S
S
→
A
b
S →
Sb
A → A
a
A →
a
left linear
S
0
→
aA
A
→ bS
A → aA
S
→ bS
S
→
ε
right linear
4) If the left linear grammar has
S
→
Ap
, then
add the following rule to the right linear
grammar:
A
→
p
Equivalent!
22
S
0
→
S
S
→
A
b
S →
Sb
A → A
a
A →
a
left linear
S
0
→
aA
A
→ bS
A → aA
S
→ bS
S
→
ε
right linear
Both grammars generate this language: {a+
b
+
}
Will the algorithm always work?
•
We have seen two examples where the
algorithm creates a right linear grammar that
is equivalent to the left linear grammar.
•
But will the algorithm
always
produce an
equivalent grammar?
•
Yes! The following slide shows why.
23
Generate string p
•
Let p = a string generated by the left linear
grammar.
•
We will show that the grammar generated by
the algorithm also produces p.
24
Case 1: the start symbol produces p
Suppose the left linear grammar has this rule:
S
→
p. Then the right linear grammar will
have the same rule (see 1 below). So the right
linear grammar will also produce p.
1)
If the left linear grammar contains S
→
p, then put that rule in the right linear grammar.
2)
If the left linear grammar contains A
→
p, then put this rule in the right linear grammar: S
→
pA
3)
If the left linear grammar contains B
→
Ap, then put this rule in the right linear grammar: A
→
pB
4)
If the left linear grammar contains S
→
Ap, then put this rule in the right linear grammar: A
→
p
Algorithm:
25
Case 2: multiple rules needed
to produce p
Suppose p is produced by a sequence of
n
production rules:
S
→
A
1
p
1
→
A
2
p
2
p
1
→
A
3
p
3
p
2
p
1
→
…
→
A
n-1
p
n-1
…p
3
p
2
p
1
→
p
n
p
n-1
…p
3
p
2
p
1
p (
p is composed of n symbols
)
26
Case 2 (continued)
S
→
A
1
p
1
→
A
2
p
2
p
1
→
A
3
p
3
p
2
p
1
→
…
→
A
n-1
p
n-1
…p
3
p
2
p
1
→
p
n
p
n-1
…p
3
p
2
p
1
Let’s see what right linear rules will be generated
by the algorithm for the rules implied by this
production sequence.
27
Algorithm inputs and outputs
algorithm
left linear rules
right linear rules
28
Case 2 (continued)
1)
If the left linear grammar contains S
→
p, then put that rule in the right linear grammar.
2)
If the left linear grammar contains A
→
p, then put this rule in the right linear grammar: S
→
pA
3)
If the left linear grammar contains B
→
Ap, then put this rule in the right linear grammar: A
→
pB
4)
If the left linear grammar contains S
→
Ap, then put this rule in the right linear grammar: A
→
p
Algorithm:
S
→
A
1
p
1
→
A
2
p
2
p
1
→
A
3
p
3
p
2
p
1
→
…
→
A
n-1
p
n-1
…p
3
p
2
p
1
→
p
n
p
n-1
…p
3
p
2
p
1
S
→
A
1
p
1
algorithm
A
1
→
p
1
(see 4 below)
29
Case 2 (continued)
1)
If the left linear grammar contains S
→
p, then put that rule in the right linear grammar.
2)
If the left linear grammar contains A
→
p, then put this rule in the right linear grammar: S
→
pA
3)
If the left linear grammar contains B
→
Ap, then put this rule in the right linear grammar: A
→
pB
4)
If the left linear grammar contains S
→
Ap, then put this rule in the right linear grammar: A
→
p
Algorithm:
S
→
A
1
p
1
→
A
2
p
2
p
1
→
A
3
p
3
p
2
p
1
→
…
→
A
n-1
p
n-1
…p
3
p
2
p
1
→
p
n
p
n-1
…p
3
p
2
p
1
A
1
→
A
2
p
2
algorithm
A
2
→
p
2
A
1
(see 3 below)
30
Case 2 (continued)
S
→
A
1
p
1
→
A
2
p
2
p
1
→
A
3
p
3
p
2
p
1
→
…
→
A
n-1
p
n-1
…p
3
p
2
p
1
→
p
n
p
n-1
…p
3
p
2
p
1
S
→
A
1
p
1
A
1
→
A
2
p
2
algorithm
A
1
→
p
1
A
2
→
p
2
A
1
31
Case 2 (continued)
S
→
A
1
p
1
A
1
→
A
2
p
2
algorithm
A
1
→
p
1
A
2
→
p
2
A
1
From A
2
we obtain p
2
p
1
:
A
2
→
p
2
A
1
→
p
2
p
1
32
Case 2 (continued)
1)
If the left linear grammar contains S
→
p, then put that rule in the right linear grammar.
2)
If the left linear grammar contains A
→
p, then put this rule in the right linear grammar: S
→
pA
3)
If the left linear grammar contains B
→
Ap, then put this rule in the right linear grammar: A
→
pB
4)
If the left linear grammar contains S
→
Ap, then put this rule in the right linear grammar: A
→
p
Algorithm:
S
→
A
1
p
1
→
A
2
p
2
p
1
→
A
3
p
3
p
2
p
1
→
…
→
A
n-1
p
n-1
…p
3
p
2
p
1
→
p
n
p
n-1
…p
3
p
2
p
1
A
2
→
A
3
p
3
algorithm
A
3
→
p
3
A
2
(see 3 below)
33
Case 2 (continued)
S
→
A
1
p
1
→
A
2
p
2
p
1
→
A
3
p
3
p
2
p
1
→
…
→
A
n-1
p
n-1
…p
3
p
2
p
1
→
p
n
p
n-1
…p
3
p
2
p
1
S
→
A
1
p
1
A
1
→
A
2
p
2
A
2
→
A
3
p
3
algorithm
A
1
→
p
1
A
2
→
p
2
A
1
A
3
→
p
3
A
2
34
Case 2 (continued)
S
→
A
1
p
1
A
1
→
A
2
p
2
A
2
→
A
3
p
3
algorithm
A
1
→
p
1
A
2
→
p
2
A
1
A
3
→
p
3
A
2
From A
3
we obtain p
3
p
2
p
1
:
A
3
→
p
3
A
2
→
p
3
p
2
A
1
→
p
3
p
2
p
1
35
Case 2 (continued)
1)
If the left linear grammar contains S
→
p, then put that rule in the right linear grammar.
2)
If the left linear grammar contains A
→
p, then put this rule in the right linear grammar: S
→
pA
3)
If the left linear grammar contains B
→
Ap, then put this rule in the right linear grammar: A
→
pB
4)
If the left linear grammar contains S
→
Ap, then put this rule in the right linear grammar: A
→
p
Algorithm:
S
→
A
1
p
1
→
A
2
p
2
p
1
→
A
3
p
3
p
2
p
1
→
…
→
A
n-1
p
n-1
…p
3
p
2
p
1
→
p
n
p
n-1
…p
3
p
2
p
1
A
n-1
→
p
n
algorithm
S
→
p
n
A
n-1
(see 2 below)
36
Case 2 (concluded)
S
→
A
1
p
1
A
1
→
A
2
p
2
A
2
→
A
3
p
3
…
A
n-1
→
p
n
algorithm
A
1
→
p
1
A
2
→
p
2
A
1
A
3
→
p
3
A
2
…
A
n-1
→
p
n-1
A
n-2
S
→
p
n
A
n-1
From S we obtain p
n
…p
2
p
1
:
S
→
p
n
A
n-1
→
p
n
p
n-1
A
n-2
→
…
→
p
n
p
n-1
…p
3
A
2
→
p
n
p
n-1
…p
3
p
2
A
1
→
p
n
…p
3
p
n-1
p
2
p
1
(
this is the desired string, p
)
37
We have shown that for any string p
generated by the left linear grammar,
the right linear grammar produced by
the algorithm will also generate p.
38
How we understand the algorithm
S
→
A
1
p
1
A
1
→
A
2
p
2
A
2
→
A
3
p
3
…
A
n-1
→
p
n
algorithm
A
1
→
p
1
A
2
→
p
2
A
1
A
3
→
p
3
A
2
…
A
n-1
→
p
n-1
A
n-2
S
→
p
n
A
n-1
These rules descend through the non-terminals until
reaching a rule with terminals on the RHS, the terminals
are output, then we unwind from the descent and output
the terminals.
Make the rule with terminals on the RHS the starting rule
and output its terminals. Ascend through the other rules.
39
How we understand the algorithm
S
→
A
1
p
1
A
1
→
A
2
p
2
A
2
→
A
3
p
3
…
A
n-1
→
p
n
algorithm
A
1
→
p
1
A
2
→
p
2
A
1
A
3
→
p
3
A
2
…
A
n-1
→
p
n-1
A
n-2
S
→
p
n
A
n-1
If the left linear grammar contains A
→
p,
then put this rule in the right linear grammar:
S
→
pA
40
How we understand the algorithm
S
→
A
1
p
1
A
1
→
A
2
p
2
A
2
→
A
3
p
3
…
A
n-1
→
p
n
algorithm
A
1
→
p
1
A
2
→
p
2
A
1
A
3
→
p
3
A
2
…
A
n-1
→
p
n-1
A
n-2
S
→
p
n
A
n-1
If the left linear grammar contains B
→
Ap,
then put this rule in the right linear grammar:
A
→
pB
41
How we understand the algorithm
S
→
A
1
p
1
A
1
→
A
2
p
2
A
2
→
A
3
p
3
…
A
n-1
→
p
n
algorithm
A
1
→
p
1
A
2
→
p
2
A
1
A
3
→
p
3
A
2
…
A
n-1
→
p
n-1
A
n-2
S
→
p
n
A
n-1
If the left linear grammar contains S
→
Ap,
then put this rule in the right linear grammar:
A
→
p
42
Left-linear grammars generate
Type 3 languages
•
Every left-linear grammar can be converted to
an equivalent right-linear grammar.
–
“Equivalent right-linear grammar” means the
grammar generate the same language.
•
Right-linear grammars generate Type 3
languages.
•
Therefore, every left-linear grammar
generates a Type 3 language.
43
Acknowledgement
The algorithm shown in these slides comes from
the wonderful book:
Introduction to Formal Languages
by Gyorgy Revesz
44
Learn about linear grammars, left linear grammars, and right linear grammars. Discover why left linear grammars are considered complex and how right linear grammars offer a simpler solution. Explore the process of converting a left linear grammar to a right linear grammar using a specific algorithm.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
How to convert a left linear grammar to a right linear grammar Roger L. Costello May 28, 2014
Objective This mini-tutorial will answer these questions: 1. What is a linear grammar? What is a left linear grammar? What is a right linear grammar? 2
Objective This mini-tutorial will answer these questions: 1. What is a linear grammar? What is a left linear grammar? What is a right linear grammar? 2. Left linear grammars are evil why? 3
Objective This mini-tutorial will answer these questions: 1. What is a linear grammar? What is a left linear grammar? What is a right linear grammar? 2. Left linear grammars are evil why? 3. What algorithm can be used to convert a left linear grammar to a right linear grammar? 4
Linear grammar A linear grammar is a context-free grammar that has at most one non-terminal symbol on the right hand side of each grammar rule. A rule may have just terminal symbols on the right hand side (zero non-terminals). Here is a linear grammar: S aA A aBb B Bb 5
Left linear grammar A left linear grammar is a linear grammar in which the non-terminal symbol always occurs on the left side. Here is a left linear grammar: S Aa A ab 6
Right linear grammar A right linear grammar is a linear grammar in which the non-terminal symbol always occurs on the right side. Here is a right linear grammar: S abaA A 7
Left linear grammars are evil Consider this rule from a left linear grammar: A Babc Can that rule be used to recognize this string: abbabc We need to check the rule for B: B Cb | D Now we need to check the rules for C and D. This is very complicated. Left linear grammars require complex parsers. 8
Right linear grammars are good Consider this rule from a right linear grammar: A abcB Can that rule be used to recognize this string: abcabb We immediately see that the first part of the string abc matches the first part of the rule. Thus, the problem simplifies to this: can the rule for B be used to recognize this string : abb Parsers for right linear grammars are much simpler. 9
Convert left linear to right linear Now we will see an algorithm for converting any left linear grammar to its equivalent right linear grammar. left linear right linear S Aa A ab S abaA A Both grammars generate this language: {aba} 10
May need to make a new start symbol The algorithm on the following slides assume that the left linear grammar doesn t have any rules with the start symbol on the right hand side. If the left linear grammar has a rule with the start symbol S on the right hand side, simply add this rule: S0 S 11
Symbols used by the algorithm Let S denote the start symbol Let A, B denote non-terminal symbols Let p denote zero or more terminal symbols Let denote the empty symbol 12
Algorithm 1) If the left linear grammar has a rule S p, then make that a rule in the right linear grammar 2) If the left linear grammar has a rule A p, then add the following rule to the right linear grammar: S pA 3) If the left linear grammar has a rule B Ap, add the following rule to the right linear grammar: A pB 4) If the left linear grammar has a rule S Ap, then add the following rule to the right linear grammar: A p 13
Convert this left linear grammar left linear S Aa A ab 14
Right hand side has terminals left linear right linear S Aa A ab S abA 2) If the left linear grammar has this rule A p, then add the following rule to the right linear grammar: S pA 15
Right hand side of S has non-terminal left linear right linear S Aa A ab S abA A a 4) If the left linear grammar has S Ap, then add the following rule to the right linear grammar: A p 16
Equivalent! left linear right linear S Aa A ab S abA A a Both grammars generate this language: {aba} 17
Convert this left linear grammar original grammar left linear S0 S S Ab S Sb A Aa A a S Ab S Sb A Aa A a make a new start symbol Convert this 18
Right hand side has terminals right linear left linear S0 aA S0 S S Ab S Sb A Aa A a 2) If the left linear grammar has this rule A p, then add the following rule to the right linear grammar: S pA 19
Right hand side has non-terminal right linear left linear S0 aA A bS A aA S bS S0 S S Ab S Sb A Aa A a 3) If the left linear grammar has a rule B Ap, add the following rule to the right linear grammar: A pB 20
Right hand side of start symbol has non-terminal right linear left linear S0 aA A bS A aA S bS S S0 S S Ab S Sb A Aa A a 4) If the left linear grammar has S Ap, then add the following rule to the right linear grammar: A p 21
Equivalent! right linear left linear S0 aA A bS A aA S bS S S0 S S Ab S Sb A Aa A a Both grammars generate this language: {a+b+} 22
Will the algorithm always work? We have seen two examples where the algorithm creates a right linear grammar that is equivalent to the left linear grammar. But will the algorithm always produce an equivalent grammar? Yes! The following slide shows why. 23
Generate string p Let p = a string generated by the left linear grammar. We will show that the grammar generated by the algorithm also produces p. 24
Case 1: the start symbol produces p Suppose the left linear grammar has this rule: S p. Then the right linear grammar will have the same rule (see 1 below). So the right linear grammar will also produce p. Algorithm: If the left linear grammar contains S p, then put that rule in the right linear grammar. If the left linear grammar contains A p, then put this rule in the right linear grammar: S pA If the left linear grammar contains B Ap, then put this rule in the right linear grammar: A pB If the left linear grammar contains S Ap, then put this rule in the right linear grammar: A p 1) 2) 3) 4) 25
Case 2: multiple rules needed to produce p Suppose p is produced by a sequence of n production rules: S A1p1 A2p2p1 A3p3p2p1 An-1pn-1 p3p2p1 pnpn-1 p3p2p1 p (p is composed of n symbols) 26
Case 2 (continued) S A1p1 A2p2p1 A3p3p2p1 An-1pn-1 p3p2p1 pnpn-1 p3p2p1 Let s see what right linear rules will be generated by the algorithm for the rules implied by this production sequence. 27
Algorithm inputs and outputs left linear rules algorithm right linear rules 28
Case 2 (continued) S A1p1 A2p2p1 A3p3p2p1 An-1pn-1 p3p2p1 pnpn-1 p3p2p1 S A1p1 algorithm A1 p1 (see 4 below) Algorithm: If the left linear grammar contains S p, then put that rule in the right linear grammar. If the left linear grammar contains A p, then put this rule in the right linear grammar: S pA If the left linear grammar contains B Ap, then put this rule in the right linear grammar: A pB If the left linear grammar contains S Ap, then put this rule in the right linear grammar: A p 1) 2) 3) 4) 29
Case 2 (continued) S A1p1 A2p2p1 A3p3p2p1 An-1pn-1 p3p2p1 pnpn-1 p3p2p1 A1 A2p2 algorithm A2 p2A1 (see 3 below) Algorithm: If the left linear grammar contains S p, then put that rule in the right linear grammar. If the left linear grammar contains A p, then put this rule in the right linear grammar: S pA If the left linear grammar contains B Ap, then put this rule in the right linear grammar: A pB If the left linear grammar contains S Ap, then put this rule in the right linear grammar: A p 1) 2) 3) 4) 30
Case 2 (continued) S A1p1 A1 A2p2 S A1p1 A2p2p1 A3p3p2p1 An-1pn-1 p3p2p1 pnpn-1 p3p2p1 algorithm A1 p1 A2 p2A1 31
Case 2 (continued) S A1p1 A1 A2p2 algorithm A1 p1 A2 p2A1 From A2 we obtain p2p1: A2 p2A1 p2p1 32
Case 2 (continued) S A1p1 A2p2p1 A3p3p2p1 An-1pn-1 p3p2p1 pnpn-1 p3p2p1 A2 A3p3 algorithm A3 p3A2 (see 3 below) Algorithm: If the left linear grammar contains S p, then put that rule in the right linear grammar. If the left linear grammar contains A p, then put this rule in the right linear grammar: S pA If the left linear grammar contains B Ap, then put this rule in the right linear grammar: A pB If the left linear grammar contains S Ap, then put this rule in the right linear grammar: A p 1) 2) 3) 4) 33
Case 2 (continued) S A1p1 A1 A2p2 A2 A3p3 S A1p1 A2p2p1 A3p3p2p1 An-1pn-1 p3p2p1 pnpn-1 p3p2p1 algorithm A1 p1 A2 p2A1 A3 p3A2 34
Case 2 (continued) S A1p1 A1 A2p2 A2 A3p3 algorithm A1 p1 A2 p2A1 A3 p3A2 From A3 we obtain p3p2p1: A3 p3A2 p3p2A1 p3p2p1 35
Case 2 (continued) S A1p1 A2p2p1 A3p3p2p1 An-1pn-1 p3p2p1 pnpn-1 p3p2p1 An-1 pn algorithm S pnAn-1 (see 2 below) Algorithm: If the left linear grammar contains S p, then put that rule in the right linear grammar. If the left linear grammar contains A p, then put this rule in the right linear grammar: S pA If the left linear grammar contains B Ap, then put this rule in the right linear grammar: A pB If the left linear grammar contains S Ap, then put this rule in the right linear grammar: A p 1) 2) 3) 4) 36
Case 2 (concluded) S A1p1 A1 A2p2 A2 A3p3 An-1 pn algorithm A1 p1 A2 p2A1 A3 p3A2 An-1 pn-1An-2 S pnAn-1 From S we obtain pn p2p1: S pnAn-1 pnpn-1An-2 pnpn-1 p3A2 pnpn-1 p3p2A1 pn p3pn-1p2p1 (this is the desired string, p) 37
We have shown that for any string p generated by the left linear grammar, the right linear grammar produced by the algorithm will also generate p. 38
How we understand the algorithm S A1p1 A1 A2p2 A2 A3p3 An-1 pn These rules descend through the non-terminals until reaching a rule with terminals on the RHS, the terminals are output, then we unwind from the descent and output the terminals. algorithm A1 p1 A2 p2A1 A3 p3A2 An-1 pn-1An-2 S pnAn-1 Make the rule with terminals on the RHS the starting rule and output its terminals. Ascend through the other rules. 39
How we understand the algorithm S A1p1 A1 A2p2 A2 A3p3 An-1 pn algorithm If the left linear grammar contains A p, then put this rule in the right linear grammar: S pA A1 p1 A2 p2A1 A3 p3A2 An-1 pn-1An-2 S pnAn-1 40
How we understand the algorithm S A1p1 A1 A2p2 A2 A3p3 An-1 pn algorithm If the left linear grammar contains B Ap, then put this rule in the right linear grammar: A pB A1 p1 A2 p2A1 A3 p3A2 An-1 pn-1An-2 S pnAn-1 41
How we understand the algorithm S A1p1 A1 A2p2 A2 A3p3 An-1 pn If the left linear grammar contains S Ap, then put this rule in the right linear grammar: A p algorithm A1 p1 A2 p2A1 A3 p3A2 An-1 pn-1An-2 S pnAn-1 42
Left-linear grammars generate Type 3 languages Every left-linear grammar can be converted to an equivalent right-linear grammar. Equivalent right-linear grammar means the grammar generate the same language. Right-linear grammars generate Type 3 languages. Therefore, every left-linear grammar generates a Type 3 language. 43
Acknowledgement The algorithm shown in these slides comes from the wonderful book: Introduction to Formal Languages by Gyorgy Revesz 44
