Natural and Context-free Languages (CFLs)/Ambiguity contest
Rony
Chapter14AlgorithmsandDecisionProceduresforContext-freeLanguagesFile.pptAlgorithms and Decision Procedures for
Context-Free Languages
Chapter 14
Decision Procedures for CFLs
Membership: Given a language L and a string w, is w in L?
Two approaches:
● If L is context-free, then there exists some context-free
grammar G that generates it. Try derivations in G and see
whether any of them generates w.
Problem:
● If L is context-free, then there exists some PDA M that
accepts it. Run M on w.
Problem:
Decision Procedures for CFLs
Membership: Given a language L and a string w, is w in L?
Two approaches:
● If L is context-free, then there exists some context-free
grammar G that generates it. Try derivations in G and see
whether any of them generates w.
S S T | a Try to derive aaa
S
S T
S T
Decision Procedures for CFLs
Membership: Given a language L and a string w, is w in L?
Two approaches:
● If L is context-free, then there exists some context-free
grammar G that generates it. Try derivations in G and see
whether any of them generates w.
Problem:
● If L is context-free, then there exists some PDA M that
accepts it. Run M on w.
Problem:
Using a Grammar
decideCFLusingGrammar(L: CFL, w: string) =
1. If given a PDA, build G so that L(G) = L(M).
2. If w = then if SG is nullable then accept, else reject.
3. If w then:
3.1 Construct G in Chomsky normal form such that
L(G) = L(G) – {}.
3.2 If G derives w, it does so in 2|w| - 1 steps. Try all
derivations in G of 2|w| - 1 steps. If one of them
derives w, accept. Otherwise reject.
Using a PDA
Recall CFGtoPDAtopdown, which built:
M = ({p, q}, , V, , p, {q}), where contains:
● The start-up transition ((p, , ), (q, S)).
● For each rule X s1s2…sn. in R, the transition ((q, , X), (q,
s1s2…sn)).
● For each character c , the transition ((q, c, c), (q, )).
Can we make this work so there are no -transitions? If every transition consumes an input character then M would have to halt after |w| steps.
Greibach Normal Form
All rules are of the following form:
● X a A, where a and A (V - )*.
No need to push the a and then immediately pop it.
So M = ({p, q}, , V, , p, {q}), where contains:
1. The start-up transitions:
For each rule S cs2…sn, the transition:
((p, c, ), (q, s2…sn)).
2. For each rule X cs2…sn (where c and s2
through sn are elements of V - ), the transition:
((q, c, X), (q, s2…sn))
A PDA Without -Transitions Must Halt
Consider the execution of M on input w:
● Each individual path of M must halt within |w| steps.
● The total number of paths pursued by M must be
less than or equal to P = B|w|, where B is the
maximum number of competing transitions from
any state in M.
● The total number of steps that will be executed by
all paths of M is bounded by P |w|.
So all paths must eventually halt.
An Algorithm to Decide Whether M Accepts w
decideCFLusingPDA(L: CFL, w: string) =
1. If L is specified as a PDA, use PDAtoCFG to construct a
grammar G such that L(G) = L(M).
2. If L is specified as a grammar G, simply use G.
3. If w = then if SG is nullable then accept, otherwise reject.
4. If w then:
4.1 From G, construct G such that L(G) = L(G) – {} and
G is in Greibach normal form.
4.2 From G construct a PDA M such that L(M) = L(G)
and M has no -transitions.
4.3 All paths of M are guaranteed to halt within a finite
number of steps. So run M on w. Accept if it accepts
and reject otherwise.
Emptiness
Given a context-free language L, is L = ?
Emptiness
Given a context-free language L, is L = ?
decideCFLempty(G: context-free grammar) =
1. Let G = removeunproductive(G).
2. If S is not present in G then return True
else return False.
Finiteness
Given a context-free language L, is L infinite?
decideCFLinfinite(G: context-free grammar) =
1. Lexicographically enumerate all strings in * of length
greater than bn and less than or equal to bn+1 + bn.
2. If, for any such string w, decideCFL(L, w) returns True
then return True. L is infinite.
3. If, for all such strings w, decideCFL(L, w) returns False
then return False. L is not infinite.
Why these bounds?
Equivalence of DCFLs
Theorem: Given two deterministic context-free languages
L1 and L2, there exists a decision procedure to determine
whether L1 = L2?
Proof: Given in [Sénizergues 2001].
The Undecidable Questions about CFLs
● Is L = *?
● Is the complement of L context-free?
● Is L regular?
● Is L1 = L2?
● Is L1 L2?
● Is L1 L2 = ?
● Is L inherently ambiguous?
● Is G ambiguous?
