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.