[go: up one dir, main page]
Scribd
Upload
13 views2 pages

Toc Unit 3 Notes

The document discusses normal forms in grammar, specifically Chomsky Normal Form (CNF) and Greibach Normal Form (GNF), explaining their structures and providing examples. It also defines ambiguity in grammars, stating that a grammar is ambiguous if a word can be derived in multiple ways. Additionally, it outlines the closure properties of context-free languages, noting their closure under union, concatenation, and Kleene closure, while indicating they are not closed under intersection or complement.

Uploaded by

yashlanjewar370
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
13 views2 pages

Toc Unit 3 Notes

The document discusses normal forms in grammar, specifically Chomsky Normal Form (CNF) and Greibach Normal Form (GNF), explaining their structures and providing examples. It also defines ambiguity in grammars, stating that a grammar is ambiguous if a word can be derived in multiple ways. Additionally, it outlines the closure properties of context-free languages, noting their closure under union, concatenation, and Kleene closure, while indicating they are not closed under intersection or complement.

Uploaded by

yashlanjewar370
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Q .2)What is normal form ? Or. Define Chomsky normal form with an example. Ques 3) When is a grammar said to be ambiguous?

Or Define Greibach normal form. Ans: Ambiguity/Ambiguous Grammars A grammar G is said to be ambiguous if
there is some word in L(G) generated by more than one leftmost derivation or
Ans: Normal Forms
rightmost derivation. In other words a grammar G is said to be ambiguous if there
A normal form is a specific format for productions, because it is specific, it is easier to analyze, and it is some word inL(G) has atleast two derivation trees.
must allow all context-free languages to be generated by a grammar in that normal form. Normal form
Definition. -- > A terminal string w in L(G) is ambiguous if there exists two or more
grammars are easy to handle and are useful in proving results.
derivation trees for w (or there exist two or more leftmost derivation of w). A
Types of Normal Forms context-free grammar G is ambiguous if there exists some w in L(G) which is
ambiguous. For example, consider, e.g., G=({S} ,{ a, b,+, *} ,P,S) , where P consists
1)Chomsky Normal Form(CNF): In the Chomsky normal form, we have restrictions on the length of of S→ S+ S|S *S| * a |b. following are the possible ambiguous derivation trees of
R.H.S. and the nature of symbols in the R.H.S. of productions. A context-free grammar G is in Chomsky G.
normal form if every production is of the form A -> a or A →BC, and SA is in G if Ae L(G).
We have two derivation trees for a + ab given in figure 3.1.
When A is in L(G), we assume that S does not appear on the R.H.S. of any production. For example,
consider G whose production are S -> AB A, A -> a, B -> b . Then G is in Chomsky normal form. The leftmost derivations of a + a*b induced by the two derivation trees are,

For a grammar in CNF, the derivation tree has the following property: Every node has atmost two S → S+S → a+S → a + S*S→ a+a*S⇒a+a*b
descendants – either two internal vertices or a single leaf.
S → S * S → S+S*S → a+S*S → a+a*S → a + a * b
2) Greibach Normal Form(GNF): A context-free grammar is in Greibach normal form if every production
Therefore, a + ab is ambiguous.
is of the form A 9 emptyset where alpha in V N ^ * and a in Sigma (α may be ε), and S -> Lambda is in G if
AE L(G). .

When Lambda in L(G) we assume that S does not appear on the R.H.S. of any production. For example, G
given by S aAB |^ , A -> bC , B -> b , C -> c is in GNF.

Ques 2) Write closure properties of CFL.

Ans: Closure Properties of CFLs The context free languages are closed under some operation means after
performing that particular operation on those CFLs the resultant language is context free language.
These properties are as below:

1)The context free languages are closed under union.

2) The context free languages are closed under concatenation.

3)The context free languages are closed under kleen closure

4) The context free languages are not closed under Intersection.

5) The context free languages are not closed under Complement.

You might also like