Q149: CFG for a’s followed by b’s and c’s such that #a = #b + #c

Question 149: What is the CFG for {a^i b^j c^k | i = j + k}?

A) S -> ∈ | aSc | X

X -> ab | aXb

B) S -> aXc

X -> aYc

Y -> ab | aYb

C) S -> aXc

X -> aYc | ac

Y -> ab | aYb

D) S -> ∈ | aXc | X

X -> ab | aSb

Solution: The correct answer is A. From the first production, we are ensuring that for every c, we get an a. From second production, we ensure that for every ‘b’, we get an ‘a’.

Q133: Language of the following CFG

Question 133: What is the language of the following grammar?

1. All strings of a’s followed by b’s, or b’s followed by a’s.
2. All strings having equal number of a’s and b’s
3. All strings having twice number of a’s than b’s.
4. None of these

Solution:

The correct answer is option 2. For every ‘a’, we get a ‘b’ as per both of the productions.

Q82: Context free grammar for the expression below

Question 83: What is the CFG for {a^i b^j | i <= 2j }?

1. S -> aaXb | aXb

X -> aXb | aaXb | ∈

2. S -> aaXb | aXb | Xb

X -> aXb | aaXb | ∈ | Xb

3. S -> aaXb | aXb

X -> aXb | aaXb | ∈ | Xb

4. S -> aaXb | Xb

X -> aaXb | ∈ | Xb

Solution: Grammar from option 1 & 3 can’t produce string ‘bb’ which is valid. Grammar from option D can’t produce string ‘ab’ which is valid.The correct answer is option 2.

Q34: Context free grammar contd.

This question is in continuation of the previous questions 29 and 30

Question #34: If we remove production 4 in the grammar mentioned in 29 , which of the following will be hampered?

A)     Production 4 is used to enforce priority, e.g. in the string 6 + 7 * 8, if we want to perform the addition first, we must use brackets in this way (6 + 7) * 8.

B)      Production 4 is used to enforce priority, e.g. in the string 6 + 7 * 8, if we want to perform the multiplication first, we must use brackets in this way 6 + (7 * 8).

C)      Production 4 is present in above grammar because it makes the strings non-ambiguous, they don’t add any power to the language.

D)     None of the above.

 

Solution:

Multiplication anyways has higher priority than addition operator, brackets are required in cases where we want to reverse the priority. Hence, the correct answer is A

Q30: Context Free Grammar Example Contd.

This question is in continuation of the previous question 29

Question #30: What is the language of the variable E?

A)     E represents the arithmetic expressions e.g. a+b or a * (a + b) where the symbols can only be a or b.

B)      E represents the arithmetic expressions e.g. a+b or a * (a + b) where the symbols can be 0, 1, a and b, but must start with a or b.

C)      E represents the arithmetic expressions where ‘+’ and ‘*’ can appear equal number of times.

D)     None of the above.

 

Solution:

The above CFG can be used to represent any arithmetic expression involving addition and multiplication. Since E can be derived to I, any arithmetic expression which start with ‘a’ or ‘b’ and having symbols ‘a’, ‘b’, ‘0’ and ‘1’ can be derived. Hence, the correct answer is B.

Q9: Context Free Grammar

Question #9: What does the following grammar represent?

Options:

1. All strings which start with 0 and end with 1.
2. All strings whose only first and last symbol is same.
3. All strings that reads the same forward and backward.
4. All strings of 0 and 1.

 

Solution:

First three rules are the basis and 4^th and 5^th rule can form any string by appending same symbol before and after the string. These strings are known as palindrome strings. Hence, the correct answer is option 3.