Q121: Variables of CFG

Question #121: Which of the following statements are true about variables of CFG?

1. The language of the variables of CFG can’t be regular language.
2. The language of the variables of CFG can be regular as well as context free language.
3. There is no language of the variables of CFG.
4. Only start symbol has the language, which is context free language.

 

Solution:

All variables have a language and they can represent regular language as well. Regular language is a subset of context free language. Hence, the correct answer is option 2.

Q89: Null closure on transaction

This question is in continuation with Q86

Question #89: Starting from state 0, with input a, what all states can be reached?

1. 3, 6, 1, 2, 4, 8, 7
2. 3, 6, 1, 2, 5, 8, 7
3. 0, 3, 6, 1, 2, 4, 8, 7
4. 3, 6, 2, 4, 8, 7

Solution: As the null closure of state 0 is 0,1,2,4,7, you can reach on states 3, 6, 1, 2, 4, 8, 7 after applying a and null transitions. The correct answer is option 1.

Q41: Yet another DFA

Question #41: What is the language of the DFA below?

 

Options:

1. L = {w | w has an even number of b’s and each a is followed by at least one b}
2. L = {w | w has an even number of a’s and each b is followed by at least one a}
3. L = {w | w has an even number of b’s and each b is followed by at least one a}
4. L = {w | w has an even number of a’s and each a is followed by at least one b}

Solution:

1C and 2C are dead states because once we go them, we can never reach final state. After every transaction of a, we have at least one transition of b, hence each a is followed by at least one b. Also, we have even number of a’s to reach to final state. Hence, the correct answer is option 4.

Q37: Regular expression for city name

Question #37: Which of the following text represent the regular expression

[A-Z][a-z]*[ ][A-Z][A-Z]?

 

Options:

A)     Bangalore KR

B)      Palo Alto CA

C)      New Delhi

D)     NDLS

 

Solution:

The above mentioned regular expression says that first word should start with a capital letter, then it is followed by a space and then the last word only has two capital letters. Only A option satisfies these constraints. This regular expression is usually used to represent city name followed by state name. Hence, the correct answer is A.

Q29: Context free grammar example

Question #29:

Following productions represent the context free grammar, where E is the start symbol and {0, 1, a, b} represent the terminal symbols.

What is the language of the variable I?

 

Options:

A)     I represents the regular language of the form (a + b)(a + b + 0 + 1)*

B)      I represents the regular language of the form (a + b + 0 + 1)*(a + b)

C)      I represents the context free language of the form a(a + b + 0 + 1)*a + b(a + b + 0 + 1)*b

D)     I represents the context free language of strings of the form of palindrome.

 

Solution:

Since the first symbol is I in the productions 7, 8, 9 and 10, and I can only be reduced to a or b, hence the final strings that are accepted must start with a or b. Hence, the correct answer is A.

Q10: Language of DFA

Question #10: What is the language of the DFA below?

 

Options:

1. All string having even number of 0’s
2. (1*01*01*)*
3. All strings which end with 1 + empty string
4. Both options 1 and 2

Solution: The above DFA accepts strings of  even number of 0’s, making option 1 the only correct answer. Note that option 2 is incorrect because it doesn’t include the string (1)* which is included in the DFA.