### AT c - Western Michigan University

```Western Michigan University
CS6800 Advanced Theory of Computation
Spring 2014
By
Abduljaleel Alhasnawi & Rihab Almalki
» Grammar: G = (V, , R, S)
Terminals and
Nonterminals
Terminals
V = {A, B, C , a ,b, c}
 = { a, b }
Start Symbol
S
Rules
R=S→A
» Rules: X  Y , where:
» X  V- 
» Ex: S  aS
» Y : , a, A, aB
» G1: R= S  aS | 
......?
» G2: R= S  aSa | bSb |  ....?
» G3: R= S  SS | (S) |  ......?
» Rules: X  Y , where:
» X  V-  and |X| = 1
» Ex: S  aS
» Y  V*
» Ex: S  
S  aSb
»
Aa
A  bBBa
»
AB
S  SS
»
A  aB
S  ABCD
» A grammar G is ambiguous iff there is at least
one string in L(G) for which G produces more
than one parse tree.
» Ex:
» Bal = { w  {),(}*: the parentheses are balanced}
» G = {{S,),(}, {),(}, R, S} , where:
» R = S  SS | (S) | 
For a string (())() , we have more than one parse trees
Assignment#6
Abduljaleel Alhasnawi
12
S
S
(
S
S
(
S

)
(
S
)

)
» Chomsky Normal Form (CNF)
» Def.: A context-free grammar G = (V, Σ, R, S) is said
to be in Chomsky Normal Form (CNF), iff every rule
in R is of one of the following forms:
» X  a where a   , or
» X  BC where B and C  V-
» Greibach Normal Form (GNF)
» Def.: GNF is a context free grammar G = (V, , R, S),
where all rules have one of the following forms:
» X  a where a   and   (V-)*
» There exists 5-steps algorithm to convert a CFG G
into a new grammar Gc such that: L(G) = L(Gc) – {}
» convertChomsky(G:CFG) =
» 1- G' = removeEps(G:CFG)
S
» 2- G'' = removeUnits(G':CFG)
AB
» 3- G''' = removeMixed(G'':CFG)
A  aB
» 4- G'v = removeLong(G''' :CFG)
S  ABCD
» 5- G'v : L(G) = L(G'v) – {}
Gv = atmostoneEps(G'v:CFG) S* S, S  
»
»
»
»
»
»
»
»
»
»
»
Find the set N of nullable variables in G.
X is nullable iff either X   or
(X  A , A  ) : X  
Ex1: G: S  aACa
AB|a
BC|c
C  cC | 
Now, since C , C is nullable
since B  C , B is nullable
since A  B , A is nullable
Therefore N = { A,B,C}
» According to N, the rules will be:
»
S  aACa
»
AB|a|
»
BC|c|
»
C  cC | 
» Now, removeEps returns G':
»
S  aACa | aAa | aCa | aa
»
AB|a
»
BC|c
»
C  cC | c
» Def.: unit production is a rule whose right
hand side consists of a single nonterminal
symbol. Ex: A  B
» Remove any unit production from G'.
» Consider the remain rules
» Ex1(continue), G‘:
»
S  aACa | aAa | aCa | aa
»
AB|a
»
BC|c
»
C  cC | c
»
»
»
»
»
»
»
»
»
Now by apply removeUnits(G':CFG) :
Remove A  B But B  C | c, so Add A  C | c
Remove B  C Add B  cC (B  c, already there)
Remove A  C Add A  cC (A  c, already there)
So removeUnits returns G'' :
S  aACa | aAa | aCa | aa
A  a | c | cC
B  c | cC
C  cC | c
» Def.: mixed is a rule whose right hand side consists of
combination of terminals or terminals with
nonterminal symbol.
» Create a new nonterminal Ta for each terminal a  
» For each Ta , add the rule Ta  a
» Ex1(continue), G'' :
»
S  aACa | aAa | aCa | aa
»
A  a | c | cC
»
B  c | cC
»
C  cC | c
» Now, by apply removeMixed(G'':CFG), G''' :
» S  TaACTa | TaATa | TaCTa | TaTa
»
A  a | c | T cC
»
B  c | T cC
»
C  T cC | c
»
Ta  a
»
Tc  c
» Def.: long is a rule whose right hand side consists of
more than two nonterminal symbol.
» R: A  BCDE
» By remove long, it will be:
» A  BM2
» M2 CM3
» M3 DE
» Ex1(continue), G'' :
»
S  aACa | aAa | aCa | aa
»
A  a | c | cC
»
B  c | cC
»
C  cC | c
» Ex1(continue), G''' :
» S  TaACTa | TaATa | TaCTa | TaTa
»
A  a | c | T cC
»
B  c | T cC
»
C  T cC | c
»
Ta  a
»
Tc  c
» Now, by apply removeLong(G''' :CFG), G'v :
»
»
»
»
»
»
»
S  TaS1 |TaS3 |TaS4 |TaTa
S1  AS2 S2  CTa S3  ATa
A  a | c | TcC
B  c | TcC
C  TcC | c
Ta  a
Tc  c
S4  CTa
» Finally, atmostoneEps(G'v:CFG) does not apply in
Ex1, Gv = G'v since L does not contain  (S is not
»
»
»
»
»
»
»
nullable).
S  TaS1 |TaS3 |TaS4 |TaTa
S1  AS2 S2  CTa S3  ATa
A  a | c | TcC
B  c | TcC
C  TcC | c
Ta  a
Tc  c
S4  CTa
» Convert the following CFG to CNF:
» S  ABC
» A  aC | D
» B  bB |  | A
» C  Ac |  | Cc
» D  aa
»
»
»
»
»
»
»
»
»
N = {A,B,C} So
add S  AB|BC|AC, A  a, B  b, C  c
delete B  , C  
The result is:
S  ABC| AB|BC|AC
A  aC | D|a
B  bB | A|b
C  Ac | Cc| c
D  aa
» S  ABC| AB|BC|AC
» A  aC | D |a (A  D, D  aa) remove A  D
add A  aa
» B  bB | A|b (B  A, A  aC|aa|a) remove B  A
add B  aC|aa|a
» C  Ac | Cc|c
» D  aa
» S  ABC| AB|BC|AC
» A  aC | aa |a
» B  bB | aC|aa|a|b
» C  Ac | Cc|c
» D  aa
» S  ABC| AB|BC|AC
» A  TaC | TaTa |a
» B  TbB | TaC| TaTa |a|b
» C  ATc | CTc|c
» D  TaTa
»
»
»
»
»
»
»
»
»
S  AM2|M2| AC|AB
M2  BC
A  TaC | TaTa |a
B  TbB | TaC| TaTa |a |b
C  ATc | CTc|c
D  TaTa
Ta  a
Tb  b
Tc  c
»
»
»
»
»
»
»
»
»
S  AM2|M2| AC|AB
M2  BC
A  TaC | TaTa |a
B  TbB | TaC| TaTa |a |b
C  ATc | CTc|c
D  TaTa
Ta  a
Tb  b
Tc  c
»
»
»
»
»
»
»
»
»
Convert the following CFG to CNF:
A → BAB | B | ε
B → 00 | ε
1- remove epsilon:
A → BAB | B | BB | AB | BA
B → 00
2- remove units:
A → BAB | 00 | BB | AB | BA
B → 00
» 3- remove mixed
» A → BC | T0T0 | BB | AB | BA
» C → AB, B → T0T0, T0 → 0
» 4- Add epsilon
» A → BC | T0T0 | BB | AB | BA | 
» C → AB
» B → T0T0
» T0 → 0
» Which one is Chomsky Normal Form ? Why?
S  AS
S a
S  AS
S  AAS
A  SA
Ab
A  SA
A  aa
Chomsky
Normal Form
Not Chomsky
Normal Form
» Convert the following CFG to CNF:
Introduce new variables for the terminals:
Ta ,Tb ,Tc
S  ABTa
S  ABa
A  aab
B  Ac
A  TaTaTb
B  ATc
Ta  a
Tb  b
Tc  c
Introduce new intermediate variable
to break first production:
S  ABTa
A  TaTaTb
B  ATc
Ta  a
Tb  b
Tc  c
V1
S  AV1
V1  BTa
A  TaTaTb
B  ATc
Ta  a
Tb  b
Tc  c
Introduce intermediate variable:
S  AV1
V1  BTa
A  TaTaTb
B  ATc
Ta  a
Tb  b
Tc  c
V2
S  AV1
V1  BTa
A  TaV2
V2  TaTb
B  ATc
Ta  a
Tb  b
Tc  c
Final grammar in Chomsky Normal Form:
S  AV1
Initial grammar
S  ABa
A  aab
B  Ac
V1  BTa
A  TaV2
V2  TaTb
B  ATc
Ta  a
Tb  b
Tc  c
»
»
»
»
»
»
»
Convert the following CFG to CNF:
EE+T
ET
TTF
TF
F  (E)
F  id
»
»
»
»
»
»
»
Remove E  T , add E  T  F |F
Remove E  F , add E  (E) | id
Remove T  F , add T  (E) | id
The result:
E  E + T | T  F | (E) | id
T  T  F | (E) | id
F  (E) | id
»
»
»
»
»
»
»
E  E T+ T | T T F | T(E T)| id
T  T T F | T(E T)| id
F  T(E T)| id
T(  (
T) )
T+  +
T*  *
»
»
»
»
»
»
»
»
»
»
E  E M2 | T M3 | T( M4 | id
T  T M3 | T(M4 | id
F  T( M4 | id
M2  T + T
M3  T * F
M4  E T )
T(  (
T) )
T+  +
T*  *
»
»
»
»
»
»
»
»
»
»
E  E M2 | T M3 | T( M4 | id
T  T M3 | T(M4 | id
F  T( M4 | id
M2  T+ T
M3  T* F
M4  E T)
T(  (
T) )
T+  +
T*  *
» Elaine A. Rich (2008) Automata, Computability,
and Complexity: Theory and Applications,
Pearson Prentice Hall.
» https://cs.wmich.edu/~elise/courses/cs680/pres
entations.htm
```