Determining GNF and CNF

Eliminate ∈ - productions from the grammar

THEORY OF AUTOMATA - JUNE 2013 - PAPER III

36. The grammar with production rules S →aSb |SS|λ generates language L given by :
(A) L = {w∈{a, b}* | n_a(w) = n_b(w) and n_a(v) ≥ n_b(v) where v is any prefix of w}
(B) L = {w∈{a, b}* | n_a(w) = n_b(w) and n_a(v) ≤ n_b(v) where v is any prefix of w}
(C) L = {w∈{a, b}* | n_a(w) ≠ n_b(w) and n_a(v) ≥ n_b(v) where v is any prefix of w}
(D)L = {w∈{a, b}* | n_a(w) ≠ n_b(w) and n_a(v) ≤ n_b(v) where v is any prefix of w}

Ans:- A

Explanation:-
Understanding and solving automata problems, will be a challenge. But if we understand the basics, solving these problems will not be a problem at all.
In order to derive the language L given a grammar with production rules, start deriving some strings starting with the start symbol S.

Example:-
Given the production rules,
S-> a S b | SS | λ

Let us start a derivation,

S -> a S b
-> a S S b ( After applying the production rule S -> SS)
-> a a S b S b ( After applying the production rule S -> a S b )
-> a a b S b (After applying the rule S -> λ)
->a a b b ( After applying the rule S -> λ)
So, we get the string, aabb which is accepted by the language.

Let us look at another derivation. (Always start with the start symbol)

S-> SS
-> a S b S ( After applying the rule S->aSb)
->a S b a S b (After applying the rule S->a S b)
->a b a S b (After applying the rule S -> λ)
->a b a b ( After applying the rule S-> λ)
So, we get the string abab, which is accepted by the language.

You can apply the production rules in any order, any number of times, you will get strings which are of the above two kinds. That is the number of ‘a’ and ‘b’ in the string will be the same.

L = {w∈{a, b}* | n_a(w) = n_b(w) and n_a(v) ≥ n_b(v) where v is any prefix of w}

In the above expression, L stands for the language. w is string of terminals. w is made up of zero or more occurrence of ‘a’ and ‘b’s. na(w) = nb(w) means the number of ‘a’ in the string w is equal to the number of ‘b’s which is true. Now, for understanding the second part of the expression, v is any prefix of w.
A prefix is a string of any number of leading symbols. For example, the string xyz has prefix (empty string), x, xy, xyz. When we consider the prefix v of w, the number of ‘a’s in it is either greater than or equal to ‘b’s in the string w.
For example, aab is prefix of the string aabb. Here, number of ‘a’s is more than the number of ‘b’s.
ab is a prefix of the string abab. The number of ‘a’ and ‘b’ are equal.
So, when we consider the prefix v, the number of ‘a’s and ‘b’s are equal. So, the correct answer is option A. In option B, the first part is correct, but the prefix part is wrong. Option C and D says that the string w will have unequal number of ‘a’ and ‘b’s which is not possible with the production rules given.
So, try to get some strings by applying the production rules, starting with the start symbol. Look for a pattern emerging in all those strings and try to answer these kind of questions.

---

37. A pushdown automation M = (Q,Σ, Γ, δ, q0, z, F) is set to be deterministic subject to which of the following condition(s), for every q ∈Q, a ∈Σ∪{λ} and b ∈Γ
(s1) δ(q, a, b) contains at most one element
(s2) if δ(q, λ, b) is not empty then δ(q, c, b) must be empty for every c ∈Σ

(A) Only s1
(B) Only s2
(C) Both s1 and s2
(D) Neither s1 nor s2

Ans:- C

Explanation:-
A DFA or NFA recognizes only regular language. They do not recognize context free languages. The automaton to recognize the CFL may require additional amount of storage which will be used to store the data. Since the DFA’s or NFA’s cannot count and cannot store the input for future reference, we are forced to have a new machine called Pushdown Automaton(PDA). PDA is an NFA with the exception that PDA has an extra stack. PDA is of two types, Deterministic and non deterministic. Unless otherwise explicitly mentioned, a PDA is non deterministic. The definition will be easier for you to understand if you know NFA better. Please refer to a good book on Theory of automata for understanding the basics well(I recommend Padma Reddy for the beginners).

The definition is understood in the following manner.
M = (Q,Σ, Γ, δ, q0, z, F)
M stands for the pushdown automaton.
Q is set of finite states
Σ – set of input alphabets
Γ – set of stack alphabets
δ - Transition function
q0 is the start state of the machine
z is the initial symbol on the stack
F is the set of final states.
In order for the PDA to be deterministic,both the conditions s1 and s2 must be satisfied. So, the correct answer is option C.

TYPES OF GRAMMAR

A grammar G is 4-tuple or quadruple G=(V,T,P,S) where
V is set of variables or non-terminals.
T is set of terminals.
P is set of productions.
S is the start symbol.
Each production is of the form α -> β where α is a non empty string of terminals and/or non-terminals and β is string of terminals and/or non-terminals including the null string. This grammar is also called as phase-structure grammar.

CHOMSKY HIERARCHY

Phase-structure grammars may be classified according to their productions. The following table would help you understand with the classifications.

S.no	TYPE	NAME	PRODUCTION RULE	RESTRICTION	LANGUAGE GENERATED	MACHINE WHICH RECOGNISES
1	Type 0 grammar	Unrestricted grammar	α -> β	No restriction on length of α and β.α cannot be epsilon	type o language or recursively enumerable language	Turing machine
2	Type 1 grammar	Context sensitive grammar	α -> β	Length of β must be atleast as much as the length of α	Type 1 language or context sensitive language	Linear Bounded automata
3	Type 2 grammar	Context free grammar	A->α	The symbol epsilon can appear on the right side of any production.	type 2 language or context free language	Pushdown automaton
4	Type 3 grammar	Regular grammar	A->wB and/or A->w		Regular language	Finite state automaton

Following are the questions from previous NET exams on the above topic.

DECEMBER 2006
JUNE 2005
JUNE 2010
32. Which of the following is the most general phase-structure grammar?
A)Regular B)Context-sensitive
C)Context free
D)Syntax tree or D) None of these
Ans:-B
Explanation:- The above question has appeared in more than 3 previous papers. The right answer is Context-sensitive grammar.

DECEMBER 2007
3) A context free grammar is :
A)type 0
B)type 1
C)type 2
Ans:- C

DECEMBER 2009
34). Context free grammar(CFG) can be recognised by
A)Finite state automaton
B)2-way linear bounded automata
C)Push down automata
D)Both B & C
Ans:- C

JUNE 2013 - PAPER III - QNo. 39
Match the following :
a. Context sensitive language     i. Deterministic finite automation
b. Regular grammar      ii. Recursive enumerable
c. Context free grammar     iii. Recursive language
d. Unrestricted grammar     iv. Pushdown automation

Ans:-

Unrestricted grammar is Recursive enumerable which is also type 0.
Context free grammar is recognised by pushdown automation
Regular grammar is recognised by Deterministic finite automation
Context sensitive language would be recursive language which is also type 1 grammar.
Choose the appropriate option by looking at the answer.

FINITE AUTOTMATA QUESTIONS

This post gives the question and answer for the subject FINITE AUTOMATA from all the previous year question papers of UGC NET.
First the year in which the question appears would be mentioned followed by the question and its answer.

DECEMBER 2004

1. The context-free languages are closed for :
(i) Intersection    (ii) Union
(iii) Complementation   (iv) Kleene Star
then
(A) (i) and (iv)    (B) (i) and (iii)
(C ) (ii) and (iv)    (D) (ii) and (iii)

Ans:-C

Explanation:- Context-free languages are closed under union,intersection and star-closure. Context-free languages are not closed under intersection and complementation.

---

June - 2005

2. Which of the following is not true ?
(A) Power of deterministic automata is equivalent to power of non-deterministic automata.
(B) Power of deterministic pushdown automata is equivalent to power of non-deterministic pushdown automata.
(C) Power of deterministic turing machine is equivalent to power of non-deterministic
turing machine. (D) All the above

Ans:-B

Explanation:- Deterministic and nondeterministic finite automata have equivalent computational capabilities.
Deterministic and nondeterministic Turing machines have the same computational capabilities.
However, the computational capabilities of deterministic push-down automata are less than those of nondeterministic push-down automata. So, the answer is B.

---

3. Identify the language which is not context - free.
(A) L={wwR|w is a member of {0,1}*}
(B) L={aⁿbⁿ|n>=0}
(C )L={ww|w is a member of {0,1}*}
(D) L={aⁿb^mc^mdⁿ|n,m>=0}

Ans:-B

---

December 2005

4. Which sentence can be generated by S → d/bA, A → d/ccA :
(A) bccddd
(B) aabccd
(C) ababccd
(D) abbbd

Ans:-A

Explanation:- The most closest answer seems to be A only. The terminals in the grammar are d,b and c. There is no terminal 'a' at all. So the options B,C and D are ruled out. option A can also be derived at something like this.
S->bA
->bccA
->bccccA
->bccccd
So the sentence generated should be bccccd. If there are any other explanations for the same please post them.

---

5. Regular expression a+b denotes the set :
(A) {a}
(B) {Epsilon, a, b}
(C) {a, b}
(D) None of these

Ans:-C

---

June 2006

6. Which of the following strings is in the language defined by grammar
S → OA, A → 1A/0A/1
(A) 01100
(B) 00101
(C ) 10011
(D) 11111

Ans:-B

Explanation:- Non terminals in the above grammar are S, and A. Terminals are 0 and 1. The start symbol of the grammar is S. S->0A. So rule out strings beginning with 1. so that leaves us with two options A and B. S->0A
->00A
->001A
->0010A
->00101
So the option B is correct. If you try to derive the string for option A you would not be able to get it. So, the correct answer is option A.

---

7. The logic of pumping lemma is a good example of :
(A) pigeon hole principle
(B) recursion
(C) divide and conquer technique
(D) iteration

Ans:-A

---

December - 2006

8. Which of the regular expressions corresponds to this grammar ? S → AB/AS, A → a/aA, B → b
(A) aa*b+
(B) aa*b
(C ) (ab)*
(D) a(ab)*

Ans:-B

---

JUNE 2007

9. The regular expression given below describes :
r=(1+01)*(0+λ)
(A) Set of all string not containing '11'
(B) Set of all string not containing '00'
(C) Set of all string containing '01'
(D) Set of all string ending in '0'

Ans:-B

Explanation:-
The meaning of (1+01)* means that the set of strings of 1 and 01 of any length including the NULL string. (0+λ) means either 0 or λ. So the full regular expression stands for the set of strings of 1's and 01's of any length ending with 0 or λ. So we cannot say the string will only end in '0'. It could end in λ also. The string can begin with 1 or 01 and multiple times it can get repeated.But the string '11' cannot be together. So the option could be B.

---