Thoery of computaion(b.TECH 4TH sEM)
Unit-2
Context-Free Grammar
1.
Context Free Grammar is formal grammar, the syntax or
structure of a formal language can be described using context-free grammar
(CFG).
2. G is context free if every production is of the form A->α, where A ∊ Vn
and α ∊ (Vn ∪ T)*.
3. The grammar has four
tuples: G = (Vn, T, P, S).
V - It is the collection of variables or nonterminal symbols. It is denoted by capital letters
T - It is a set of terminals. It is denoted by lower case letters.
P - It is the production rules that consist of both terminals and nonterminal.
S - It is the Starting symbol.
4. left-hand side of the G, here
in the example can only be a Variable, it cannot be a terminal or variable in
only capital letter.
5. But on the right-hand side
here it can be a Variable or Terminal or both combination of Variable and
Terminal.
6. Example the grammar A = {
S, a,b, P,S} having production :
·
Here
S is the starting symbol.
·
{a,b}
are the terminals generally represented by small characters.
·
P
is variable along with S
· S-> aS
S-> bSa
7. a->bSa, or
a->ba is not a CFG as on the left-hand side there is a variable which does not follow the CFGs rule.
Limitations of Context-Free Grammar
1. CFGs are less expressive,
and neither English nor programming language can be expressed using
Context-Free Grammar.
2. Context-Free Grammar can be
ambiguous means we can generate multiple parse trees of the same input.
Derivation tree
1. Derivation tree is a
graphical representation for the derivation of the given production rules of
the context free grammar (CFG).
2. It is a way to show how
the derivation can be done to obtain some string from a given set of production
rules. It is also called as the Parse tree.
Properties
The properties of the derivation tree are given
below −
- The
root node is always a node indicating the start symbols.
- The
derivation is read from left to right.
- The
leaf node is always the terminal node.
- The
interior nodes are always the non-terminal nodes.
Example:-
Let
G=({S,A},{A,B},P, S ) where P consist of
Sà aAS |a | SS, Aà SbA | ba and construct tree whose yield aabaa .
 |
Question:- Let G be the grammar S--> OB | 1A., A -->0 | 0S |1AA, B--> 1| 1S | OBB. For the string 00110101, find (a) the leftmost
derivation, (b) the rightmost derivation, and (c) the derivation tree.
Solution
Ambiguous Context Free Grammar:
1. A context free grammar is called ambiguous
if there exists more than one LMD(left most derivation) or more than one
RMD(right most derivation) for a string
which is generated by grammar. There will also be more than one derivation tree
for a string in ambiguous grammar.
2. A terminal string W E L(G) is ambiguous if
there exist two or more derivation trees for w (or there exist two or more
leftmost derivations of w). Consider, for example, G = ({S}, {a, b, +, *}, P.
S), where P consists of 5 -7 5 + 5 IS * 5 Ia Ib. We have two derivation trees
for a + a " b given in Fig.
Chomsky's Normal
Form (CNF)
1. CNF stands
for Chomsky normal form. A CFG(context free grammar) is in CNF(Chomsky normal
form) if all production rules satisfy one of the following conditions:
o Start symbol generating ε. For example, S → ε.
o A non-terminal generating two non-terminals. For
example, S → AB.
o A non-terminal generating a terminal. For example,
S → a.
For example:
1. G1 = {S → AB, S → c, A → a, B → b}
2. G2 = {S → aA, A → a, B → c}
The production rules of Grammar G1 satisfy the rules specified for CNF,
so the grammar G1 is in CNF. However, the production rule of Grammar G2 does
not satisfy the rules specified for CNF as S → aZ contains terminal followed by
non-terminal. So the grammar G2 is not in CNF.
Steps for converting CFG into CNF
Step 1: Eliminate start symbol from the RHS. If
the start symbol T is at the right-hand side of any production,
create a new production as: S1 → S Where S1 is
the new start symbol.
Step
2: In the grammar, remove the null, unit and useless
productions
Step
3: Eliminate terminals from the RHS of the production if
they exist with other non-terminals or terminals. For example, production S →
aA can be decomposed as:
S → RA
R → a
Step 4: Eliminate RHS
with more than two non-terminals. For example, S → ASB can be decomposed as:
S → RS
R → AS
Greibach
Normal Form (GNF)
GNF
stands for Greibach normal form. A CFG(context free grammar) is in GNF(Greibach
normal form) if all the production rules satisfy one of the following
conditions:
o A
start symbol generating ε. For example, S → ε.
o A
non-terminal generating a terminal. For example, A → a.
o A
non-terminal generating a terminal which is followed by any number of
non-terminals. For example, S → aASB.
For
example:
G1 = {S → aAB | aB, A → aA| a, B → bB | b}
G2 = {S → aAB | aB, A → aA | ε, B → bB | ε}
The production rules of Grammar G1 satisfy the rules
specified for GNF, so the grammar G1 is in GNF. However, the production rule of
Grammar G2 does not satisfy the rules specified for GNF as A → ε and B → ε
contains ε(only start symbol can generate ε). So the grammar G2 is not in GNF.
Steps for converting
CFG into GNF:-
Step 1: Convert the grammar into CNF. If the
given grammar is not in CNF, convert it into CNF
Step 2: If the grammar
exists left recursion, eliminate it.
If the
context free grammar contains left recursion, eliminate it. You can refer the
following topic to eliminate left recursion: Left Recursion
Step 3: In the grammar,
convert the given production rule into GNF form.
If any production rule in the grammar is not in GNF form, convert it.
Convert CFG to GNF
SàAB
AàaA | bB | b
Bàb
solution:-
SàAB
this is not in gnf so convert CNF the GNF
So Substitute the value of A in S production
rule
i.e SàAab | Bbb | bB
AàaA | bB | b ( this
is already in GNF)
Bàb (this is already in GNF)
New GNF production are:-
SàAab | Bbb | bB
AàaA | bB | b
Example:
S → XB | AA
A → a | SA
B → b
X → a
Solution:
As the given grammar G
is already in CNF and there is no left recursion, so we can skip step 1 and
step 2 and directly go to step 3.
1.The production rule A
→ SA is not in GNF, so we substitute S → XB | AA in the production rule A → SA
as
S → XB | AA
A → a | XBA | AAA
B → b
X → a
3. The
production rule S → XB and B → XBA is not in GNF, so we substitute X → a in the
production rule S → XB and B → XBA as:
S → aB | AA
A → a | aBA | AAA
B → b
X → a
3.Now we will remove left recursion (A → AAA),
we get:
S → aB | AA
A → aC | aBAC
C → AAC | ε
B → b
X → a
4.Now we will remove null production C → ε, we
get:
S → aB | AA
A → aC | aBAC | a | aBA
C → AAC | AA
B → b
X → a
5.The production rule S → AA is not in GNF, so
we substitute A → aC | aBAC | a | aBA in production rule S → AA as:
S → aB | aCA | aBACA | aA | aBAA
A → aC | aBAC | a | aBA
C → AAC
C → aCA | aBACA | aA | aBAA
B → b
X → a
6.The production rule C → AAC is not in GNF, so
we substitute A → aC | aBAC | a | aBA in production rule C → AAC as:
S → aB | aCA | aBACA | aA | aBAA
A → aC | aBAC | a | aBA
C → aCAC | aBACAC | aAC | aBAAC
C → aCA | aBACA | aA | aBAA
B → b
X → a
Hence, this is the GNF form for the grammar G.
Unit-3
Pushdown
Automata(PDA)
A pushdown automata (PDA) is more powerful than FA(finite automata). Any language which can be acceptable by FA(finite automata). can also be acceptable by PDA(pushdown automata).
PDA Components:
1. Input tape: The input tape is
divided in many cells or symbols. The input head is read-only and may only move
from left to right, one symbol at a time.
2.Finite control: The finite
control has some pointer which points the current symbol which is to be read.
3.Stack: The stack is a
structure in which we can push and remove the items from one end only. It has
an infinite size. In PDA, the stack is used to store the items temporarily.
Definition of PDA:
PDA is a 7-touple
namely (Q, ∑, Γ,
δ, q0,
Zo, F).
Q: the finite set of
states
∑: the input set
Γ: a stack symbol
which can be pushed and popped from the stack
q0: the initial state
Zo: a start(initial)
symbol .
F: a set of final
states
δ: mapping
function or transition function which is used for moving from current state to
next state.
Instantaneous Description (ID):-
ID is an informal
notation of how a PDA computes an input string and make a decision that string
is accepted or rejected.
An instantaneous
description is a triple (q, w, α) where:
q
- describes
the current state.
w - describes the
remaining input.
α - describes the
stack contents, top at the left.
Turnstile Notation:
1. ⊢ sign describes the
turnstile notation and represents one move.
2. ⊢* sign describes a
sequence of moves.
For example:-
(p, b, T) ⊢ (q, w, α)
In the
above example, while taking a transition from state p to q, the input symbol
'b' is consumed, and the top of the stack 'T' is represented by a new string α.
Q. Design a PDA for accepting a language {anb2n |
n>=1}.
Solution: In
this language, n number of a's should be followed by 2n number of b's. Hence,
we will apply a very simple logic, and that is if we read single 'a', we will
push two a's onto the stack. As soon as we read 'b' then for every single 'b'
only one 'a' should get popped from the stack.
The
ID can be constructed as follows:
1. δ(q0, a, Z) = (q0, aaZ)
2. δ(q0, a, a) = (q0, aaa)
Now
when we read b, we will change the state from q0 to q1 and start popping
corresponding 'a'. Hence,
δ(q0, b, a) = (q1, ε)
Thus,
this process of popping 'b' will be repeated unless all the symbols are read.
Note that popping action occurs in state q1 only.
δ(q1, b, a) = (q1, ε)
After
reading all b's, all the corresponding a's should get popped. Hence when we
read ε as input symbol then there should be nothing in the stack. Hence the
move will be:
δ(q1, ε, Z) = (q2, ε)
Where
DA =
({q0, q1, q2}, {a, b}, {a, Z}, δ, q0, Z, {q2})
Q. Construct
a pda A accepting the set of all strings over {a, b} with equal number of a's
and b’s.
Solution:-
Let
A =({q), [a. b]. [Zo, a, b], D, q, Zo, 0)
where δ
is defined by the following rules:
δ (q, a, Zo) = {(q, aZo)} δ (q, b, Zo) = {(q, bZo)}
δ (q, a, a) = {(q, aa)} δ (q, b,b) = {(q, bb)}
δ (q, a, b) = {(q, ε)} δ (q, b, a) = {(q, ε)}
δ (q, A, Zo) = {(q, ε)}
Non-deterministic
Pushdown Automata
The
non-deterministic pushdown automata is very much similar to NFA. We will
discuss some CFGs which accepts NPDA.
The
CFG which accepts deterministic PDA accepts non-deterministic PDAs as well.
Similarly, there are some CFGs which can be accepted only by NPDA and not by
DPDA. Thus NPDA is more powerful than DPDA.
Q. Construct PDA for the given CFG, and test
whether 0104 is
acceptable by this PDA.
S → 0BB
B → 0S | 1S | 0
Solution:
The
PDA can be given as:
1. A = {(q), (0, 1), (S, B, 0, 1), δ, q, S, ?}
The
production rule δ can be:
R1:
δ(q, ε, S) = {(q, 0BB)}
R2:
δ(q, ε, B) = {(q, 0S) | (q, 1S) | (q, 0)}
R3:
δ(q, 0, 0) = {(q, ε)}
R4:
δ(q, 1, 1) = {(q, ε)}
Testing
0104 i.e. 010000 against PDA:
CONTEXT FREE LANGUAGES
• A context-free
language (CFL) is a language generated by some context-free
grammar (CFG).
• The
class of context-free languages generalizes the class of regular languages,
i.e., every regular language is a context-free language.
• The
reverse of this is not true, i.e., every context-free language is not
necessarily regular.
Deterministic context-free languages(DCFL);-
• Deterministic
context-free languages are a proper
subset of context-free languages.
• Context
free languages that can be accepted by Deterministic Push-Down Automata.
• DCFLs
are always unambiguous.
• Many
programming languages can be described by means of DCFLs.
Properties
of DCFL:-
• DCFLS
are not closed under union.
• DCFLS
are not closed under intersection.
• DCFLS
are closed under complement.
CFL
HIERARCHY;-
Closure Properties of Context Free Languages
1. Context-free
languages are closed under −
- Union
- Concatenation
- Kleene
Star operation
Union
Let L1 and
L2 be two context free languages. Then L1 ∪ L2 is
also context free.
Example:-
Let L1 =
{ anbn , n > 0}. Corresponding grammar G1 will
have P: S1 → aAb|ab
Let L2 =
{ cmdm , m ≥ 0}. Corresponding grammar G2 will
have P: S2 → cBb| ε
Union of L1 and
L2, L = L1 ∪ L2 = { anbn }
∪ {
cmdm }
The corresponding
grammar G will have the additional production S → S1 | S2
Concatenation
If L1 and L2 are
context free languages, then L1L2 is also context
free.
Example
Union of the languages L1 and L2,
L = L1L2 = { anbncmdm }
The corresponding grammar G will have the
additional production S → S1 S2
Kleene
Star
If L is a context free language, then L* is also context
free.
Example
Let L = { anbn , n ≥ 0}.
Corresponding grammar G will have P: S → aAb| ε
Kleene Star L1 = { anbn }*
The corresponding grammar G1 will have
additional productions S1 → SS1 | ε
2.Context-free languages are not
closed under −
·
Intersection −
If L1 and L2 are context free languages, then L1 ∩ L2 is not necessarily
context free.
·
Intersection with Regular Language − If L1 is a regular language and L2 is a context free
language, then L1 ∩ L2 is a context free language.
·
Complement −
If L1 is a context free language, then L1’ may not be context free.
Decision Properties
of CFL(Context Free Languages):-
1. Test for Membership:
Decidable.
2. Test for Emptiness: Decidable
3. Test for finiteness: Decidable
Deciding Properties
of CFL(Context Free Languages):-
For a given CFG, there
exists an algorithm to decide whether its language is finite or not.
Step-01:
Reduce the given
grammar completely by-
· Eliminating ∈ productions
· Eliminating unit productions
· Eliminating useless productions
Step-02:
· Draw a directed
graph whose nodes are variables of the given grammar.
· There exists an edge from node A to node B if there
exists a production of the form
A → αBβ.
Now, following 2 cases
are possible-
Case-01:
· Directed graph contains
a cycle.
· In this case, language
of the given grammar is infinite.
Case-02:
· Directed graph does not contain any cycle.
· In this case, language of the given grammar is finite.
Unit-4
TURING MACHINE
The Turing machine can be thought of as finite control connected to a
R/W (read/write) head. It has one tape which is divided into a number of cells.
The block diagram of the basic model for the Turing machine is given
Each cell can store only one symbol. The input to and the output from
the finite state automaton are effected by the R/W head which can examine one
cell at a time.
DefInition:-
A Turing machine M is a 7-tuple, namely (Q, ∑, Γ,
δ, q0, b, F )where
1. Q is a finite nonempty set of states.
2. Γ is a finite
nonempty set of tape symbols,
3. is the blank.
4. ∑ is a nonempty set of input symbols
5. δ is the transition
function mapping
6. 
is the initial
state, and
7. 
is the set of
final states.
REPRESENTATION OF
TURING MACHINES:-
(i)
Instantaneous descriptions
using move-relations.
(ii)
Transition table
(iii)
Transition diagram (transition
graph).
Q. Construct TM for the
language L ={0n1n} where n>=1.
Solution:
Now we will see how this turing machine work for 0011.
The simulation for 0011 can be shown as below:
Now, we will see how this turing machine will works for 0011. Initially,
state is q0 and head points to 0 as:
The move will be δ(q0, 0) = δ(q1, A, R) which means it will go to state
q1, replaced 0 by A and head will move to the right as:
The move will be δ(q1, 0) = δ(q1, 0, R) which means it will not change any
symbol, remain in the same state and move to the right as:
The move will be δ(q1, 1) = δ(q2, B, L) which means it will go to state q2,
replaced 1 by B and head will move to left as:
Now move will be δ(q2, 0) = δ(q2, 0, L) which means it will not change
any symbol, remain in the same state and move to left as:
The move will be δ(q2, A) = δ(q0, A, R), it means will go to state q0, replaced
A by A and head will move to the right as:
The move will be δ(q0, 0) = δ(q1, A, R) which means it will go to state q1,
replaced 0 by A, and head will move to right as:
The move will be δ(q1, B) = δ(q1, B, R) which means it will not change any
symbol, remain in the same state and move to right as:
The move will be δ(q1, 1) = δ(q2, B, L) which means it will go to state q2,
replaced 1 by B and head will move to left as:
The move δ(q2, B) = (q2, B, L) which means it will not change any symbol,
remain in the same state and move to left as:
Now immediately before B is A that means all the 0?s are market by A. So
we will move right to ensure that no 1 is present. The move will be δ(q2, A) =
(q0, A, R) which means it will go to state q0, will not change any symbol, and
move to right as:
The move δ(q0, B) = (q3, B, R) which means it will go to state q3, will not
change any symbol, and move to right as:
The move δ(q3, B) = (q3, B, R) which means it will not change any symbol,
remain in the same state and move to right as:
The move δ(q3, Δ) = (q4, Δ, R) which means it will go to state q4 which is the
HALT state and HALT state is always an accept state for any TM.
The same TM can be represented by Transition Diagram:
replace
replace
xàA and yàB
Chomsky Hierarchy
Chomsky
Hierarchy represents the class of languages that are accepted by the different
machine. The category of language in Chomsky's Hierarchy is as given below:
1. Type 0 known as Unrestricted Grammar.
2. Type 1 known as Context Sensitive Grammar.
3. Type 2 known as Context Free Grammar.
4. Type 3 Regular Grammar.
Type
0 Grammar:
Type
0 grammar is known as Unrestricted grammar. There is no restriction on the
grammar rules of these types of languages. These languages can be efficiently
modeled by Turing machines.
Type
1 Grammar:
Type
1 grammar is known as Context Sensitive Grammar. The context sensitive grammar
is used to represent context sensitive language.
For
example:
S → AT
T → xy
A → a
Type
2 Grammar:
Type
2 Grammar is known as Context Free Grammar. Context free languages are the
languages which can be represented by the context free grammar (CFG). Type 2
should be type 1.
For
example:
A → aBb
A → b
B → a
Type
3 Grammar:
Type 3 Grammar is known as Regular Grammar. Regular languages
are those languages which can be described using regular expressions. These
languages can be modeled by NFA or DFA.
Type 3 is most restricted form of grammar. The Type 3 grammar
should be Type 2 and Type 1. Type 3 should be in the form of
V → T*V / T*
Comments
Post a Comment