retagged by
3,335 views
2 votes
2 votes
  1. Which of the following features cannot be captured by CFG?
    1.   Syntax of if - then – else statements
    2.   Whether a variable is declared before its use
    3.   Syntax of recursive procedures
    4.   Matching nested parenthesis

pls explain about first option.how is it CFG possible??

retagged by

2 Answers

Best answer
2 votes
2 votes

The checking of if then else construct can be done by a CFG..The CFG ia written as :

S --> i C t S A

A --> ; e S | epsilon

where S stands for the statement or a block of statements in case of nesting if then else block ..i for if C for condition, t for then,  A handles the else part and there e stands for else and after that further if then else block may be there in case of nested if then else blocks and epsilon for termination condition..

Reference : http://infolab.stanford.edu/~ullman/ialc/spr10/slides/cfl1.pdf

Syntax of recursive programs can also be implemented by CFG by allowing self recursion [Productions of type S --> aS etc..]

The CFG for nested parantheses is also there..

But variable declared before use is something which cannot be done by a CFL ..As it is a CSL..

Hence 2) is the correct answer..

selected by
0 votes
0 votes

From the programming point of view CFL can't do two things

1) L={WW | W∈ (0,1)∗}

2) L={aibjcid| a,b,c,d ∈ (0,1)∗}

Now if we notice

1) is actually 'Variable declaration' (Whether variable has been declared before or not).

2) is actually matching of formal and actual parameter.

Related questions

5 votes
5 votes
1 answer
1
sh!va asked Jun 21, 2016
8,648 views
Which of the following features cannot be captured by CFGSyntax of if then else statementsSyntax of recursive proceduresWhether a variable is declared before its useMatch...
1 votes
1 votes
1 answer
3
sh!va asked Jul 1, 2016
1,222 views
Which of the following cannot be normalized in floating point representation?a 1b 0c Infinityd b and c onlye. a,b and c