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?
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.)
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 Theory Explanation. |
Question 4 |
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?
The language generated by G is (a + b)* | |
The language generated by G is a*(a + b)b* | |
The language generated by G is a*b*(a + b) | |
The language generated by G is not a regular language |
Question 5 |
S → AB
A → a
B → b
B → C
A | |
B | |
C | |
S |
Question 6 |
To obtain a string of n Terminals from a given Chomsky normal form grammar, the number of productions to be used is :
2n−1 | |
2n | |
n+1 | |
n2
|
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 |
Regular | |
Context free but non regular | |
Context sensitive but non context free | |
Type 0 but non context sensitive |
Question 8 |
If a language is context free it can always be accepted by a deterministic pushdown automaton | |
The union of two context free language is context free | |
The intersection of two context free language is context free | |
The complement of a context free language is context free |
