The Gateway to Computer Science Excellence
+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 is it CFG possible??

in Theory of Computation by Boss
retagged by | 667 views

2 Answers

+2 votes
Best answer

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 :

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..

by Veteran
selected by
thanks a lot ..:-)
can we do if else using regular grammar??
No we cannot .. As regular languages have limited power as compared to CFLs
CFG for nested parenthesis is also known as the language of proper prefix, means no proper subset of any word  w belonging to language should belong to the language.
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.

by Boss
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,221 questions
59,856 answers
118,101 users