Formal Languages and Context-free Languages

theory of computation

1. Formal Languages
Context-Free Languages
Eng Charbel Boustany
AUST -Zahle

2. 2
Regular Languages}0:{ nba
nn }{
R
ww **ba *)(ba

3. 3
Regular Languages}{
nn
ba }{
R
ww
Context-Free Languages

4. 4
Context-Free Languages
Pushdown
Automata
Context-Free
Grammars
stack
automaton

5. 5
Context-Free Grammars

6. 6
Grammars
Grammars express languages
Example: the English languageverbpredicate
nounarticlephrasenoun
predicatephrasenounsentence



_
_

7. 7walksverb
runsverb
dognoun
catnoun
thearticle
aarticle







8. 8
A derivation of “the dog walks”:walksdogthe
verbdogthe
verbnounthe
verbnounarticle
verbphrasenoun
predicatephrasenounsentence






_
_

9. 9
A derivation of “a cat runs”:runscata
verbcata
verbnouna
verbnounarticle
verbphrasenoun
predicatephrasenounsentence






_
_

10. 10
Language of the grammar:
L = { “a cat runs”,
“a cat walks”,
“the cat runs”,
“the cat walks”,
“a dog runs”,
“a dog walks”,
“the dog runs”,
“the dog walks” }

11. 11
Notationdognoun
catnoun


Variable Terminal
Production Rules

12. 12
Another Example
Grammar:
Derivation of sentence :

S
aSbS abaSbS  ab aSbS S

13. 13
Language?

14. 14aabbaaSbbaSbS  aSbS S aabb 

S
aSbS
Grammar:
Derivation of sentence :

15. 15
Other derivations:aaabbbaaaSbbbaaSbbaSbS  aaaabbbbaaaaSbbbb
aaaSbbbaaSbbaSbS



16. 16
Language of the grammar

S
aSbS }0:{  nbaL
nn

17. 17
More Notation
Grammar PSTVG ,,, :V :T :S :P
Set of variables
Set of terminal symbols
Start variable
Set of Production rules

18. 18
Example
Grammar :

S
aSbS G  PSTVG ,,, }{SV },{baT },{  SaSbSP

19. 19
More Notation
Sentential Form:
A sentence that contains
variables and terminals
Example:aaabbbaaaSbbbaaSbbaSbS 
Sentential Forms sentence

20. 20
We write:
Instead of:aaabbbS
*
 aaabbbaaaSbbbaaSbbaSbS 

21. 21
In general we write:
If:nww
*
1 nwwww  
321

22. 22
By default:ww
*


23. 23
Example

S
aSbS aaabbbS
aabbS
abS
S
*
*
*
*




Grammar Derivations

24. 24baaaaaSbbbbaaSbb
aaSbbS



 

S
aSbS
Grammar
Example
Derivations

25. 25
Another Grammar Example
Grammar :


A
aAbA
AbS
Derivations:aabbbaaAbbbaAbbAbS
abbaAbbAbS
bAbS
⇒⇒⇒⇒
⇒⇒⇒
⇒⇒ G

26. 26
Language?

27. 27
More DerivationsaaaabbbbbaaaaAbbbbb
aaaAbbbbaaAbbbaAbbAbS

 bbaS
bbbaaaaaabbbbS
aaaabbbbbS
nn







28. 28
Language of a Grammar
For a grammar
with start variable : G S }:{)( wSwGL


String of terminals

29. 29
Example
For grammar : 


A
aAbA
AbS }0:{)(  nbbaGL
nn
Since:bbaS
nn

 G

30. 30
A Convenient Notation

A
aAbA |aAbA thearticle
aarticle

 theaarticle|

31. 31
Example
A context-free grammar :

S
aSbS aabbaaSbbaSbS  G
A derivation:

32. 32
A context-free grammar :

S
aSbS aaabbbaaaSbbbaaSbbaSbS  G
Another derivation:

33. 33

S
aSbS )(GL
(((( ))))}0:{ nba
nn Describes parentheses:

34. 34 


S
bSbS
aSaS abbaabSbaaSaS 
A context-free grammar :G
A derivation:
Example

35. 35
Language?

36. 36 


S
bSbS
aSaS abaabaabaSabaabSbaaSaS 
A context-free grammar :G
Another derivation:

37. 37 


S
bSbS
aSaS )(GL }*},{:{ bawww
R


38. 38


S
SSS
aSbS ababSaSbSSSS 
A context-free grammar :G
A derivation:
Example

39. 39
Language?

40. 40


S
SSS
aSbS abababaSbabSaSbSSSS 
A context-free grammar :G
A derivation:

41. 41


S
SSS
aSbS }prefixanyin
)()( and
),()(:{
v
vnvn
wnwnw
ba
ba

 )(GL
Interpretation?

42. 42


S
SSS
aSbS }prefixanyin
)()( and
),()(:{
v
vnvn
wnwnw
ba
ba


() ((( ))) (( )))(GL
Describes
matched
parentheses:

43. 43
Definition: Context-Free Grammars
Grammar
Productions of the form:xA
String of variables
and terminals),,,( PSTVG
VariablesTerminal
symbols
Start
variable
Variable

44. 44*},:{)(
*
TwwSwGL  ),,,( PSTVG

45. 45
Definition: Context-Free Languages
A language is context-free
if and only if
there is a context-freegrammar
with L G )(GLL

46. 46
Derivation OrderABS.1 

A
aaAA
.3
.2 

B
BbB
.5
.4 aabaaBbaaBaaABABS
54321

Leftmost derivation:aabaaAbAbABbABS
32541

Rightmost derivation:

47. 47
Language?

48. 48|AB
bBbA
aABS



Leftmost derivation:abbbbabbbbB
abbBbbBabAbBabBbBaABS


Rightmost derivation:abbbbabbBbb
abAbabBbaAaABS



49. 49
Language?

50. 50
Derivation Trees

51. 51ABS ABS |aaAA |BbB S B A

52. 52ABS |aaAA |BbB aaABABS  a a A S B A

53. 53ABS |aaAA |BbB aaABbaaABABS  S B A a a A B b

54. 54ABS |aaAA |BbB aaBbaaABbaaABABS  S B A a a A B b 

55. 55ABS |aaAA |BbB aabaaBbaaABbaaABABS  S B A a a A B b  
Derivation Tree

56. 56aabaaBbaaABbaaABABS 
yieldaab
baa

 S B A a a A B b  
Derivation TreeABS |aaAA |BbB

57. 57
Partial Derivation Trees ABS S B A
Partial derivation treeABS |aaAA |BbB

58. 58aaABABS  S B A a a A
Partial derivation tree

59. 59aaABABS  S B A a a A
Partial derivation tree
sentential
form
yieldaaAB

60. 60aabaaBbaaBaaABABS  aabaaAbAbABbABS  S B A a a A B b  
Same derivation tree
Sometimes, derivation order doesn’t matter
Leftmost:
Rightmost:

61. 61
Ambiguity

62. 62aEEEEEE |)(|| aaa E E E E E  a a a  aaaEaa
EEaEaEEE
*

leftmost derivation

63. 63aEEEEEE |)(|| aaa E E E  a a  E E a aaaEaa
EEaEEEEEE


leftmost derivation

64. 64aEEEEEE |)(|| aaa E E E  a a  E E a E E E E E  a a a 
Two derivation trees

65. 65
The grammaraEEEEEE |)(||
is ambiguous:E E E  a a  E E a E E E E E  a a a 
string aaa has two derivation trees

66. 66
string aaa has two leftmost derivationsaaaEaa
EEaEEEEEE

 aaaEaa
EEaEaEEE
*

The grammaraEEEEEE |)(||
is ambiguous:

67. 67
Definition:
A context-free grammar is ambiguous
if some string has:
two or more derivation treesG )(GLw

68. 68
In other words:
A context-free grammar is ambiguous
if some string has:
two or more leftmost derivationsG )(GLw
(or rightmost)

69. 69
Why do we care about ambiguity?E E E  a a  E E a E E E E E  a a a  aaa
take2a

70. 70E E E   E E E E E E E   222 2 2 2 2 2 2

71. 71E E E   E E E E E E E   6222  2 2 2 2 2 2 8222  4 2 2 2 6 2 2 2 4 8

72. 72E E E E E   6222  2 2 2 4 2 2 2 6
Correct result:

73. 73
•We want to remove ambiguity
•Ambiguity is badfor programming languages

74. 74
We fix the ambiguousgrammar:aEEEEEE |)(||
New non-ambiguousgrammar:aF
EF
FT
FTT
TE
TEE






)(

75. 75aF
EF
FT
FTT
TE
TEE






)( aaaFaaFFa
FTaTaTFTTTEE

 E E T  T  F F a T F a a aaa

76. 76E E T  T  F F a T F a a aaa
Unique derivation tree

77. 77
The grammar : aF
EF
FT
FTT
TE
TEE






)(
is non-ambiguous:
Every string has
a unique derivation tree G )(GLw

78. 78
Another Ambiguous Grammar
IF_STMT if EXPR then STMT |
if EXPR then STMT else STMT

79. 79
If expr1then if expr2then stmt1else stmt2
IF_STMT
expr1then
elseifexpr2then
STMT
stmt1
if
IF_STMT
expr1then else
ifexpr2then
STMT stmt2if
stmt1
stmt2

80. 80
Inherent Ambiguity
Some context free languages
have only ambiguous grammars
Example:}{}{
mmnmnn
cbacbaL  |
|
11
aAbA
AcSS

 |
|
22
bBcB
BaSS

 21|SSS

81. 81
The string nnn
cba
has two derivation treesS 1S S 2S 1S c 2S a

82. 82
Ambiguity in natural language?