Context-Free Grammar

Definition − A context-free grammar (CFG) consisting of a finite set of grammar rules is a quadruple (N, T, P, S) where

• N is a set of non-terminal symbols.
• T is a set of terminals where N ∩ T = NULL.
• P is a set of rules, P: N → (N ∪ T)*, i.e., the left-hand side of the production rule P does have any right context or left context.
• S is the start symbol.

Example

• The grammar ({A}, {a, b, c}, P, A), P : A → aA, A → abc.
• The grammar ({S, a, b}, {a, b}, P, S), P: S → aSa, S → bSb, S → ε
• The grammar ({S, F}, {0, 1}, P, S), P: S → 00S | 11F, F → 00F | ε

Generation of Derivation Tree

A derivation tree or parse tree is an ordered rooted tree that graphically represents the semantic information a string derived from a context-free grammar.

Representation Technique

• Root vertex − Must be labeled by the start symbol.
• Vertex − Labeled by a non-terminal symbol.
• Leaves − Labeled by a terminal symbol or ε.

If S → x₁x₂ …… x_n is a production rule in a CFG, then the parse tree / derivation tree will be as follows −

There are two different approaches to draw a derivation tree −

Top-down Approach −

• Starts with the starting symbol S
• Goes down to tree leaves using productions

Bottom-up Approach −

• Starts from tree leaves
• Proceeds upward to the root which is the starting symbol S

Derivation or Yield of a Tree

The derivation or the yield of a parse tree is the final string obtained by concatenating the labels of the leaves of the tree from left to right, ignoring the Nulls. However, if all the leaves are Null, derivation is Null.

Example

Let a CFG {N,T,P,S} be

N = {S}, T = {a, b}, Starting symbol = S, P = S → SS | aSb | ε

One derivation from the above CFG is “abaabb”

S → SS → aSbS → abS → abaSb → abaaSbb → abaabb

Sentential Form and Partial Derivation Tree

A partial derivation tree is a sub-tree of a derivation tree/parse tree such that either all of its children are in the sub-tree or none of them are in the sub-tree.

Example

If in any CFG the productions are −

S → AB, A → aaA | ε, B → Bb| ε

the partial derivation tree can be the following −

If a partial derivation tree contains the root S, it is called a sentential form. The above sub-tree is also in sentential form.

Leftmost and Rightmost Derivation of a String

• Leftmost derivation − A leftmost derivation is obtained by applying production to the leftmost variable in each step.
• Rightmost derivation − A rightmost derivation is obtained by applying production to the rightmost variable in each step.

Example

Let any set of production rules in a CFG be

X → X+X | X*X |X| a

over an alphabet {a}.

The leftmost derivation for the string "a+a*a" may be −

X → X+X → a+X → a + X*X → a+a*X → a+a*a

The stepwise derivation of the above string is shown as below −

The rightmost derivation for the above string "a+a*a" may be −

X → X*X → X*a → X+X*a → X+a*a → a+a*a

The stepwise derivation of the above string is shown as below −

Left and Right Recursive Grammars

In a context-free grammar G, if there is a production in the form X → Xa where X is a non-terminal and ‘a’ is a string of terminals, it is called a left recursive production. The grammar having a left recursive production is called a left recursive grammar.

And if in a context-free grammar G, if there is a production is in the form X → aX where X is a non-terminal and ‘a’ is a string of terminals, it is called a right recursive production. The grammar having a right recursive production is called a right recursive grammar.

Types of Grammar in automata

According to Noam Chomosky, there are four types of grammars − Type 0, Type 1, Type 2, and Type 3. The following table shows how they differ from each other −

Grammar Type	Grammar Accepted	Language Accepted	Automaton
Type 0	Unrestricted grammar	Recursively enumerable language	Turing Machine
Type 1	Context-sensitive grammar	Context-sensitive language	Linear-bounded automaton
Type 2	Context-free grammar	Context-free language	Pushdown automaton
Type 3	Regular grammar	Regular language	Finite state automaton

Take a look at the following illustration. It shows the scope of each type of grammar −

Type - 3 Grammar

Type-3 grammars generate regular languages. Type-3 grammars must have a single non-terminal on the left-hand side and a right-hand side consisting of a single terminal or single terminal followed by a single non-terminal.

The productions must be in the form X → a or X → aY

where X, Y ∈ N (Non terminal)

and a ∈ T (Terminal)

The rule S → ε is allowed if S does not appear on the right side of any rule.

Example

X → ε 
X → a | aY
Y → b 

Type - 2 Grammar

Type-2 grammars generate context-free languages.

The productions must be in the form A → γ

where A ∈ N (Non terminal)

and γ ∈ (T ∪ N)* (String of terminals and non-terminals).

These languages generated by these grammars are be recognized by a non-deterministic pushdown automaton.

Example

S → X a 
X → a 
X → aX 
X → abc 
X → ε

Type - 1 Grammar

Type-1 grammars generate context-sensitive languages. The productions must be in the form

α A β → α γ β

where A ∈ N (Non-terminal)

and α, β, γ ∈ (T ∪ N)* (Strings of terminals and non-terminals)

The strings α and β may be empty, but γ must be non-empty.

The rule S → ε is allowed if S does not appear on the right side of any rule. The languages generated by these grammars are recognized by a linear bounded automaton.

Example

AB → AbBc 
A → bcA 
B → b 

Type - 0 Grammar

Type-0 grammars generate recursively enumerable languages. The productions have no restrictions. They are any phase structure grammar including all formal grammars.

They generate the languages that are recognized by a Turing machine.

The productions can be in the form of α → β where α is a string of terminals and nonterminals with at least one non-terminal and α cannot be null. β is a string of terminals and non-terminals.

Example

S → ACaB 
Bc → acB 
CB → DB 
aD → Db 

Normalization Explained..

Prototyping Model

The prototyping model is applied when detailed information related to input and output requirements of the system is not available. In this model, it is assumed that all the requirements may not be known at the start of the development of the system. It is usually used when a system does not exist or in case of a large and complex system where there is no manual process to determine the requirements. This model allows the users to interact and experiment with a working model of the system known as prototype. The prototype gives the user an actual feel of the system.

At any stage, if the user is not satisfied with the prototype, it can be discarded and an entirely new system can be developed. Generally, prototype can be prepared by the approaches listed below.

1. By creating main user interfaces without any substantial coding so that users can get a feel of how the actual system will appear.
2. By abbreviating a version of the system that will perform limited subsets of functions
3. By using system components to illustrate the functions that will be included in the system to be developed

 Using the prototype, the client can get an actual feel of the system. So, this case of model is beneficial in the case when requirements cannot be freezed initially. 

 This prototype is developed based on the currently known requirements. Development of the prototype obviously undergoes design, coding, and testing,  but each of these phases is not done very formally or thoroughly.

By using this prototype, the client can get an actual feel of the system, because the interactions with the prototype can enable the client to better understand the requirements of the desired system.

Paper-1 Solved Questions Series 1

1. Video-Conferencing can be classified as one of the following types of communication :

(A) Visual one way

(B) Audio-Visual one way

(C) Audio-Visual two way

(D) Visual two way

2. MC National University of Journalism and Communication is located at

(A) Lucknow

(B) Bhopal

(C) Chennai

(D) Mumbai

3. All India Radio (A.I.R.) for broadcasting was named in the year

(A) 1926

(B) 1936

(C) 1946

(D) 1956

4. In India for broadcasting TV programmes which system is followed ?

(A) NTCS

(B) PAL

(C) NTSE

(D) SECAM

5. The term ‘DAVP’ stands for

(A) Directorate of Advertising & Vocal Publicity

(B) Division of Audio-Visual Publicity

(C) Department of Audio-Visual Publicity

(D) Directorate of Advertising & Visual Publicity

6. The term “TRP” is associated with TV shows stands for

(A) Total Rating Points

(B) Time Rating Points

(C) Thematic Rating Points

(D) Television Rating Points

7. Which is the number that comes next in the following sequence ?

2, 6, 12, 20, 30, 42, 56, _____

(A) 60

(B) 64

(C) 72

(D) 70

8. Find the next letter for the series YVSP ………

(A) N

(B) M

(C) O

(D) L

9. Given that in a code language, ‘645’ means ‘day is warm’; ‘42’ means ‘warm spring’ and ‘634’ means ‘spring is sunny’; which digit represents ‘sunny’ ?

(A) 3

(B) 2

(C) 4

(D) 5

10. The basis of the following classification is :

‘first President of India’ ‘author of Godan’ ‘books in my library’, ‘blue things’ and ‘students who work hard’

(A) Common names

(B) Proper names

(C) Descriptive phrases

(D) Indefinite description

11. In the expression ‘Nothing is larger than itself’ the relation ‘is larger than’ is

(A) antisymmetric

(B) asymmetrical

(C) intransitive

(D) irreflexive

12. Assertion (A) : There are more laws on the books today than ever before, and more crimes being committed than ever before.

       Reason (R) : Because to reduce crime we must eliminate the laws.

Choose the correct answer from below :

(A) (A) is true, (R) is doubtful and (R) is not the correct explanation of (A).

(B) (A) is false, (R) is true and (R) is the correct explanation of (A).

(C) (A) is doubtful, (R) is doubtful and (R) is not the correct explanation of (A).

(D) (A) is doubtful, (R) is true and (R) is not the correct explanation of (A).

13. If the proposition “All men are not mortal” is true then which of the following inferences is correct ? Choose from the code given below :

1. “All men are mortal” is true.

2. “Some men are mortal” is false.

3. “No men are mortal” is doubtful.

4. “All men are mortal” is false.

Code :

(A) 1, 2 and 3

(B) 2, 3 and 4

(C) 1, 3 and 4

(D) 1 and 3

14. Determine the nature of the following definition :

“Abortion” means the ruthless murdering of innocent beings.

(A) Lexical

(B) Persuasive

(C) Stipulative

(D) Theoretical

15. Which one of the following is not an argument ?

(A) Devadutt does not eat in the day so he must be eating at night.

(B) If Devadutt is growing fat and if he does not eat during the day, he will be eating at night.

(C) Devadutt eats in the night so he does not eat during the day.

(D) Since Devadutt does not eat in the day, he must be eating in the night.

16. Venn diagram is a kind of diagram to

(A) represent and assess the validity of elementary inferences of syllogistic form.

(B) represent but not assess the validity of elementary inferences of syllogistic form.

(C) represent and assess the truth of elementary inferences of syllogistic form.

(D) assess but not represent the truth of elementary inferences of syllogistic form.

17. Reasoning by analogy leads to

(A) certainty

(B) definite conclusion

(C) predictive conjecture

(D) surety

18. Which of the following statements are false ? Choose from the code given below :

1. Inductive arguments always proceed from the particular to the general.

2. A cogent argument must be inductively strong.

3. A valid argument may have a false premise and a false conclusion.

4. An argument may legitimately be spoken of as ‘true’ or ‘false’.

Code :

(A) 2, 3 and 4

(B) 1 and 3

(C) 2 and 4

(D) 1 and 2

19. Six persons A, B, C, D, E and F are standing in a circle. B is between F and C, A is between E and D, F is to the left of D. Who is between A and F ?

(A) B

(B) C

(C) D

(D) E

20. The price of petrol increases by 25%. By what percentage must a customer reduce the consumption so that the earlier bill on the petrol does not alter ?

(A) 20%

(B) 25%

(C) 30%

(D) 33.33%

21. If Ram knows that y is an integer greater than 2 and less than 7 and Hari knows that y is an integer greater than 5 and less than 10, then they may correctly conclude that

(A) y can be exactly determined

(B) y may be either of two values

(C) y may be any of three values

(D) there is no value of y satisfying these conditions

22. Four pipes can fill a reservoir in 15, 20, 30 and 60 hours respectively. The first one was opened at 6 AM, second at 7 AM, third at 8 AM and the fourth at 9 AM. When will the reservoir be filled ?

(A) 11 AM

(B) 12 Noon

(C) 1 PM

(D) 1:30 PM