GATE Prev Year : Theory of Computation Test-8 for GATE & PSU CS Exams

Question 1

Which one of the following is TRUE?

Question 2

Which of the following pairs have DIFFERENT expressive power?

Question 3

Consider the following expression grammar. The seman tic rules for expression calculation are stated next to each grammar production.
E --> number E.val = number.val
| E' '+' E E⁽¹⁾ .val = E^(2).val + E^(3).val
| E' '×' E E⁽^1).val = E^(2).val × E^(3).val

The above grammar and the semantic rules are fed to a yacc tool (which is an LALR (1) parser generator) for parsing and evaluating arithmetic expressions. Which one of the following is true about the action of yacc for the given grammar?

Question 4

Consider the following expression grammar. The seman tic rules for expression calculation are stated next to each grammar production.
E --> number E.val = number.val
| E' '+' E E⁽¹⁾ .val = E^(2).val + E^(3).val
| E' '×' E E⁽^1).val = E^(2).val × E^(3).val

Assume the conflicts in Part A. of this question are resolved and an LALR (1) parser is generated for parsing arithmetic expressions as per the given grammar. Consider an expression 3 × 2 + 1. What precedence and associativity properties does the generated parser realize?

Question 5

L = {w|w∈ {a,b}*,}. Which of the following is correct if w is the string of L?

Question 6

L = {w|w∈ {a,b}*, w has an odd number of a's and an odd number of b's}

Then string length w is ?