Regular languages and FA’s
are too simple and too restrictive to handle complex problems. So Context free
Grammars had to be used to create more interesting languages.
We can solve
problems, i.e. write grammars for languages like anbn and
palindromes that we could not do in regular expressions.
Context Free grammar consists
of Non terminals, Terminals, Productions and Start symbol.
Non terminals are the non
ending states.
Terminals are the endings.
Productions are the rules
defined on that language.
Start symbol is the starting
state.
For example
1) Let’s write a Context free grammar (CFG) for anbn
Consider a variable S which
we will consider as the start state.
We can rewrite as S → ε, says
that the arbitrary string could simply be ε, obtained by substituting ε for the
variable S.
Next for anbn
, n number of a’s will be followed by n number of b’s
so we can write the next
production as S → aSb, where aSb can be substituted on place of S
So the final grammar for anbn
is,
S → aSb | ε
We can simulate any string on
these rules to check if that string belongs to the language.
eg: To simulate a3b3
So in this way we get a3b3,
therefore this string is accepted
2) Write a CFG for palindrome of even or odd length.
S → aSa (If it starts with an a, it has to end with
an a)
S → bSb (If it starts with an
b, it has to end with a b)
S → a (In odd palindrome the odd letter can be
an a)
S → b (In odd palindrome the odd letter can be
a b)
S → ε (Case
for even palindrome where there wont be an odd letter)
Therefore the CFG for
palindrome is
S → aSa | bSb | a | b | ε
eg: To simulate string abbba
on this CFG
Therefore, string abbba is
accepted.
3) Design a grammar for ai bi cj where i, j > 1
Here a and b have to come
same number of times and c can come any number of times.
S → S1S2 (Rule S1 will be done first
and then rule S2)
S1 → aS1b
| ab ( a and b can come multiple times same number
of times,
and it ends with
ab)
S2 → cS2
| c ( c can come any number of
times, and end with c )
eg: To simulate aabbc
Therefore string aabbc is
accepted.
This tree which is drawn
while simulating is also known as Parsing tree or Syntax check tree or
derivation tree.
Feel free to comment if you have any doubts.
Recommended articles:
Comments
Post a Comment