Test: Context Free Grammar - Computer Science Engineering (CSE) MCQ

The entity which accepts a language is termed as Automata while the one which generates it is called Grammar. Tokens are the smallest individual unit of a program.

Every regular language can be produced by context free grammar and context free language can be produced by context sensitive grammar and so on.

There exists no finite automata to accept the given language i.e. 0ⁿ1ⁿ. For other options, it is possible to make a dfa or nfa representing the language set.

L = {e, 01, 0011, 000111, ……0ⁿ1ⁿ}. As epsilon is a part of the set, thus all the options are correct implying none of them to be wrong.

Regular grammar is a subset of context free grammar and thus all regular grammars are context free.

LL(1) Grammar: The first 'L' refers to scanning of input from Left to Right, the second 'L' refers to producing the Leftmost Derivation and the (1) stands for using only 1 lookahead input symbol at each step to make parsing action decisions. Hence, a context-free grammar G = (VT, VN, S, P) whose parsing table has no multiple entries is said to be LL(1) Grammar.

LL(1) Conflicts:

• Checking whether a grammar is ambiguous or not is undecidable.
• A grammar can be LL(1) only if it is not ambiguous, not left recursive and it must not contain left factoring and vice-versa is not necessary.
• Any regular language can be LL(1) is true statement since we can write regular grammar which follows the above conflict.

Since a grammar is LL(1) only if it does not contain left recursion, ambiguity and left factoring, hence, to convert an arbitrary CFG to LL(1), all the three should be eliminated

Concept:
Chomsky's normal form:
A Chomsky normal form follows the,
V→VV (Exactly 2 non-terminals)
V is Non-terminals
V→T (Exactly one terminal)
T is terminal
If length n=1, Number of productions = 1
S→a
If length n=2, Number of productions = 3
S→AB
A→a
B→b
If length n=3, Number of productions = 5
S→AX
X→BC
A→a
B→b
C→c
According to this, If length n, the number of productions = (2n-1) is required.
n=4,
then,
(2(4)-1)= 7 productions
Hence the correct answer is 7.

Grammar G1 is:
D → int L;
L → id [E
E → num]
E → num] [E
Generate one dimensional array: a[10]
D → int L
→ int id[E
→ int id[num]
This leads to int a[10]
Generate two-dimensional array: int a [10] [3];
D → int L;
→ int id [E;
→ int id [num] [E;
→ int id [num] [num];
This leads to int a[10][3]
It correctly generates declaration given.
Grammar G2 is:
D → int L;
L → idE
E → E[num]
E → [num]
Generate one dimensional array: a[10]
D → int L;
→ int idE
→ int id[num]
This leads to int a[10]
Generate two-dimensional array: int a [10] [3];
int a[10][3];
D → int L;
→ int id E;
→ int id E[num];
→ int id [num] [num];
This leads to int a[10][3]
So, both grammar G1 and G2 generates the given declaration.

S → abScT
→ ababScTcT (∵ S → abScT)
→ abababcTcTcT (∵ S → abcT)
→ abababcbTcTcT (∵ T → bT)
→ abababcbbTcTcT (∵ T → bT)
→ abababcbbbTcTcT (∵ T → bT)
→ abababcbbbbcTcT (∵ T → b)
→ abababcbbbbcbcT (∵ T → b)
→ abababcbbbbcbcbT (∵ T → bT)
→ abababcbbbbcbcbb (∵ T → b)
abababcbbbbcbcbb = (ab)³cb⁴cbcb²
From this string, it is clear that all the option 1),3) and 4) are not generated by given grammar.

Concept:
A language is regular if we could find a corresponding regular expression that generates it and an finite automata that accepts it. A language is CFL, if we could construct a Push Down Automata (PDA) that accepts it.
L₁ = {wxyx | w, x, y ϵ (0 + 1)⁺}
L₁ is a regular language.
Since it is given that w, x, y ϵ (0 + 1)⁺}, that means w, x, y all three can be strings of {0, 1}.
L1 can be generated by a regular expression of the form:
(0+1)⁺0 (0+1)⁺0 + (0+1)⁺1 (0+1)⁺1, by putting x as 0 and 1 alternatively. Since it can be represented as a regular expression, it is a regular language.
L₂ = {xy | x, y ϵ (a + b)*, |x| = |y|, x ≠ y}
L^₂ is a Context Free Language.
L₂ consists of set of strings which could be split into two non-identical substrings, but of equal length. Since comparison is involved, it cannot be done with a finite automata. However, a PDA can do comparisons, so PDA would accept the above language. Thus L₂ is a CFL.