CSC3228: THEORY OF COMPUTATION

CONTEXT-FREE LANGUAGES (CFL)

ì Formal Definition of CFL
ì Context Free Grammar (CFG)
ì Designing CFG

CSC3113: Theory of Computation

ì Concept and Definition of Context Free Language (CFL)
ì Concept and Construct of Context Free Grammar (CFG)
ì Designing CFG

CSC3113: Theory of Computation

 ALL OUTCOME ARE REPRESENTED WITH EXAMPLES

ì Learn the concept and Formal Definition of CFL

ì Understand the construct of CFG
ì Learn and Design CFG for languages

CSC3113: Theory of Computation

CONTEXT-FREE LANGUAGES
ìContext-Free Languages includes all regular
languages and many additional languages, such as
{0n#1n | n ³ 0}.
ìAdditional memory is used to recognize such
languages.
ìContext-Free Grammars.
ìMore powerful method of describing language.
ìCan describe certain features that have a recursive
structure.

CSC3113: Theory of Computation

EXAMPLE: CONTEXT-FREE GRAMMARS
A à 0A1 A à 0A1 | B
AàB or Bà#
Bà#

ì A grammar consists of a collection of Substitution (or Production) rules.

ì Each rule appears as a line in the grammar.
ì Each line has a variable and a string separated by an arrow.
ì Variable consists of a symbol.
ì represented as uppercase letters.
ì might include index or subscript.
ì Strings consists of variables and/or other symbols called terminals.
ì terminals are analogous to input alphabet, represented as lowercase letters, numbers,
or special symbols.
ì might include index or subscript.
ì One variable is designated the start variable, usually the left-hand side of the
topmost rule.
ì Several rules for the same left-hand variable can be written using “|” as an “or”.

CSC3113: Theory of Computation

CONTEXT-FREE GRAMMARS
ì Use a grammar to describe a language by A
generating each string of the language in the
following manner –
1. Write down the start variable, s.
2. Choose a variable v from the right-hand side of the A
rule for s.
3. Find a rule that starts with (or left-hand side is) v.
4. Replace v in rule s by right-hand side of rule v.
A
5. Repeat from step 2 to 4 until no more variables
remains.
ì The sequence of substitutions to obtain a string is
called derivation. Derivation of string 000#111 in A
the grammar –
A à 0A1 | B
Bà#
B
ì AÞ 0A1Þ 00A11Þ 000A111Þ 000B111Þ 000#111
ì Using Parse Tree: Figure on the right

0 0 0 # 1 1 1

CSC3113: Theory of Computation

FORMAL DEFINITION
ì A context-free grammar is a 4-touple (V,Σ,R,S), where –
ì V is a finite set called variables,
ì Σ is a finite set, disjoint from V, called the alphabet,
ì R is a finite set of rules, with each rule being a variable and a strings of
variables and terminals, and
ì SÎV is the start variable.
ì If u, v, and w are strings of variables and terminals, and
A à w is a rule of the grammar,
we say that uAv yields uwv, written uAv Þ uwv.
ì If u = v or if a sequence u1, u2, …, uk exists for k ³ 0 and
u Þ u1 Þ u2 Þ … Þ uk Þ v, we say u yields v,
∗
written as u ⇒ v.
∗
ì The language of the grammar is 𝑤 ∈ ∑∗ | 𝑆 ⇒𝑤 .

CSC3113: Theory of Computation

DESIGNING
ìCFG that is union of simpler CFGs:
ì Break into simpler pieces and Construct individual grammars for
each piece.
ì Combine them into one grammar by putting all the rules together
and adding a new rule, S à s1 | s2 |…| sk, where the
variables si are the start variables for the individual grammars.
ìExample:
{strings containing n, n³0, number of 0s and 1s}
= {1n0n | n³0} È {0n1n | n³0}
{0n1n | n³0} can be represented S1 à 0S11 | e
{1n0n | n³0} can be represented S2 à 1S20 | e
{1n0n | n³0} È {0n1n | n³0} can be represented
S à S1 | S 2
S1 à 0S11 | e
S2 à 1S20 | e

CSC3113: Theory of Computation

DESIGNING
ì CFG for regular language:
ì Construct a DFA M=(Q, Σ, d, q0, F) for the regular language.
ì Convert the DFA M into equivalent CFG as follows –
ì Variable Ri for each state qiÎQ. Make R0 the start variable for the start state q0.
ì Add rule Ri à aRj to the CFG for each d(qi, a) = qj.
ì Example:
Language: A = {w | the sum of all the symbols in w is an even number }
DFA:
M=(Q, Σ, d, q0, F), where, Q={b0,b1}, q0=b0, F={b0},Σ={0,1,2}
d | 0 1 2
b0 | b0 b1 b0
b1 | b1 b0 b1
CFG:
Grammar G = (V, Σ, R, R0), where, V = {R0, R1}, Σ = {0, 1, 2},
and
R is the set of rules
R0 à 0R0 | 1R1 | 2R0 | e
R1 à 0R1 | 1R0 | 2R1

CSC3113: Theory of Computation

DESIGNING
ìLanguage containing strings with two substrings that are
linked or depended on each other by their number of
appearances.
ìUse rule of the form R à uRv.
ìThis generates strings wherein the portion containing the
u’s corresponds to the portion containing v’s.
ìExample:
Language: {1n0n | n³0}
CFG: S à 1S0 | e

CSC3113: Theory of Computation

DESIGNING CFG
A={ w | w begins with a and ends with b } S à aTb
T à aT | bT | Î
A={ w | w begins with b or ends with a } S à bT | Ta
T à aT | bT | Î
A={ w | w contains at least 3 a‘s } S à TaTaTaP
T à bT | Î
P à aP | bP | Î
A={ w | w contains at most 3 a‘s } S à BABABAB
Aàa|Î
B à bB | Î
A={ w | w contains the substring aba } S à TabaT
T à aT | bT | Î
A={ w | w does not contain the substring aba } S à bS | aT | Î
T à aT | bR | Î
R à bS | Î
A={ w | every odd position of w is a } S à aT | Î
T à aS | bS | Î
A={ w | w = ambn and m = n} T à aTb | Î
CSC3113: Theory of Computation
DESIGNING CFG
A={ w | w has even length } S à aT | bT
T à aP | bP
P à aT | bT | Î
A={ w | w = ambn and m > n} S à AT
T à aTb | Î
A à aA | a
A={ w | each a in w is followed by at least one b } S à BabBT
B à bB | Î
T à abBT | Î
A={ w | w has even number of a‘s and each a in w is P à BabBT
followed by at least one b } T à abBS
S à abBT | Î
B à bB | Î
A={ aibjck | where i = j or j = k and i, j, k ≥ 0} and S à PR | QT
∑ = {a, b, c} P à aPb | Î
R à cR | Î
T à bTc | Î
Q à aQ | Î
CSC3113: Theory of Computation
 CONTEXT FREE LANGUAGE & GRAMMAR
ì Introduction to Theory of Computation, Sipser, (3rd ed),
CFL-1.
ì Elements of the Theory of Computation, Papadimitriou (2nd ed),
CFL-1.
ì Introduction to Automata Theory, Languages, and Computations,
Hopcroft, CFL-1.

CSC3113: Theory of Computation