Xem mẫu
- Lecture # 25
Theory Of Automata
By
Dr. MM Alam
1
- Lecture#24 at a glance…
•
Unrestricted Grammars Example
•
User controlled Parsing in JFLAP
•
Regular Grammar Conversion to FA
- FA Conversion to Regular
grammar
EXAMPLE 3
•
Consider the CFG:
S → aaS l bbS I abXI baX I λ
X → aaX l bbX l abS l baS
•
The algorithm tells us that there will
be three states: -, X, +.
3
- FA Conversion to Regular
grammar
EXAMPLE 3
•
Since there is only one production of
the form S → aaS l bbS I abXI baX I
λ
Np → wq X → aaX l bbX l abS l baS
•
TG is
4
- FA Conversion to Regular
grammar
EXAMPLE 4
•
Consider the CFG:
S → aA | bB
A → aS | a
B → bS | b
•
This language can be defined by the regular
expression (aa + bb)+.
•
It does not have any productions of the form
Nx →ʎ
5
- Important Point
For a CFG to accept the word ʎ, it
must have at least one production of this
form, called a ʎ -production.
•
A ʎ -production need not imply that ʎ is
in the language, as with
S → aX
X→ʎ
6
- Regular Grammar
•
The corresponding TG:
S → aA | bB
A → aS | a
B → bS | b
7
- •
Regular Grammar Conversion to FA using
JFLAP
•
Practical Demonstration
- Elimination of null production
Theorem
Statement:
If L is a context-free language generated by
a CFG that includes ʎ -productions then there is
a different context-free grammar that has no ʎ
-productions that generates either the whole
language L (if L does not include the word ʎ)
or else generates the language of all the
words in L that are not ʎ.
9
- Proof (by Example)
•
Consider CFG for EVENPALINDROME
(the
•
palindromes with an even number of
letters):
S → aSa I bSb I ʎ
•
Following possible derivation:
S => aSa
=> aaSaa
=> aabSbaa 10
- Proof (Cont’d…)
•
When we apply this replacement rule
to the following CFG.
S → aSa I bSb I ʎ
•
We remove the production S → ʎ and
replace it with S → aa and S → bb,
•
These are the first two productions with
the right-side S deleted.
11
- Proof (Cont’d…)
•
The CFG is now:
S → aSa I bSb I aa I bb
•
Which also generates
EVENPALINDROME, except for the
word ʎ, which can no longer be
derived.
•
For example, the derivation is generated
in the old CFG: (Next slide)
12
- Regular Grammar
•
OLD CFG: Derivation Production
Used
S => aSa S → aSa
=> aaSaa S → aSa
=> S → bSb
aabSbaa
=> aabbaa S →ʎ
13
- Regular Grammar
•
New CFG
•
We can combine the last two steps .
Derivation Production
Used Derivation Production
Used
S => aSa S → aSa
S => S →
=> aaSaa S → aSa aSa aSa
=> S →
=> S → bSb aaSaa aSa
aabSbaa
=> S → bb
=> aabbaa S →ʎ aabbaa
14
- Null Production Elimination
EXAMPLE
•
Consider the CFG for the language
defined by (a + b)*a
S → Xa
X → aX I bX I ʎ
•
The only nullable nonterminal here is
X,
15
- Null Production Elimination
•
The productions that have right sides
including X are:
Productions with Nullables
S → Xa
X → aX
X → bX
New Productions Formed by the Rule
S→ a
X→a 16
- Null Production Elimination
•
The full new CFG is:
S → Xa I a
X → aX | bX | a I b Derivation Production
Used
•
To produce the word baa we
S => Xa S → Xa
formerly used the derivation shown=> bXa X → bX
In the table. => baXa X → aX
=> baa X →ʎ
17
- Null Production Elimination
•
Combine the last two steps, and the
new derivation in the new CFG is:
Derivation Production Derivation Production
Used Used
S => Xa S → Xa S => Xa S → Xa
=> bXa X → bX => bXa X → bX
=> baXa X → aX => baa X →a
=> baa X →ʎ
18
- Null Production Elimination
•
Consider this CFG for the language
defined by (a + b)*bb(a + b)*
S → XY
X → Zb
Y → bW
Z → AB
W→Z
A → aA I bA I ʎ
19
- Null Production Elimination
•
The modified replacement algorithm tells
us to generate new productions to replace
the ʎ -productions as follows:
Old New Productions
X → Zb X→b
Y → bW Y→b
Z → AB Z → A and Z → B
W→Z Nothing new
A → aA A→a
A → bA A→b
B → Ba B→a 20
nguon tai.lieu . vn
