Context-free-grammar

Question 1

(a) Let G1 = (N, T, P, S1) be a CFG where,
N = {S1, A, B}, T = {a,b} and
P is given by

         S1 → aS1b             S1 → aBb
         S1 → aAb              B → Bb
         A → aA                B → b
         A → a 

What is L(G1)?

(b) Use the grammar in part(a) to give a CFG
for L2 = {ai bj ak bl | i, j, k, l ≥ 1, i=j or k=l} by adding not more than 5 production rule.

(c) Is L2 inherently ambiguous?

A
Theory Explanation.
Question 2

Let G be a context-free grammar where G = ({S, A, B, C},{a,b,d},P,S) with the productions in P given below.

   S → ABAC
   A → aA ∣ ε
   B → bB ∣ ε
   C → d  

(ε denotes null string). Transform the grammar G to an equivalent context-free grammar G' that has no ε productions and no unit productions. (A unit production is of the form x → y, and x and y are non terminals.)

A
Theory Explanation.
Question 3

A simple Pascal like language has only three statements.
(i) assignment statement e.g. x:=expression
(ii) loop construct e.g. for i:=expression to expression do statement.
(iii) sequencing e.g. begin statement ;…; statement end

(a) Write a context-free grammar (CFG) for statements in the above language. Assume that expression has already been defined. Do not use optional parentheses and * operator in CFG.
(b) Show the parse tree for the following statement:

     for j:=2 to 10 do
         begin x:=expr1;
               y:=expr2
         end  
A
Theory Explanation.
Question 4
Consider the context-free grammar G below
S → aSb | X
X → aX | Xb | a | b ,
where S and X are non-terminals, and a and b are terminal symbols. The starting non-terminal is S. Which one of the following statements is CORRECT?
A
The language generated by G is (a + b)*
B
The language generated by G is a*(a + b)b*
C
The language generated by G is a*b*(a + b)
D
The language generated by G is not a regular language
Question 5
Which variable does not drive a terminal string in grammar?
S → AB
A → a
B → b
B → C
A
A
B
B
C
C
D
S
Question 5 Explanation: 
C is the useless variable as there is no production rule which replaces C with a terminal. Hence it does not derive any non terminal.
Question 6

To obtain a string of n Terminals from a given Chomsky normal form grammar, the number of productions to be used is :

A
2n−1
B
2n
C
n+1
D
n2
Question 6 Explanation: 
If all the productions of a grammar are in the form A ➝ BC OR A ➝ a then that grammar is said to be in Chomsky normal form.
Example:

Derive string “ab” from above grammar.
Sol:

Using formula 2n - 1; where n = length of string
2(2) - 1 = 3
Hence, the answer is option(1).
Question 7
The language {Wa Xb Ya+b | a,b >=1} is:
A
Regular
B
Context free but non regular
C
Context sensitive but non context free
D
Type 0 but non context sensitive
Question 7 Explanation: 
It is context free grammar but not regular because it requires to solve one stack of memory.
Question 8
Which of the following statements is true?
A
If a language is context free it can always be accepted by a deterministic pushdown automaton
B
The union of two context free language is context free
C
The intersection of two context free language is context free
D
The complement of a context free language is context free
Question 8 Explanation: 
Context free languages closed under Union, concatenation and kleene star. But not close under intersection and complementation.
There are 8 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access