The Gateway to Computer Science Excellence
+2 votes
441 views
  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??

in Theory of Computation by Boss (12.2k points)
retagged by | 441 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 : 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..

by Veteran (101k points)
selected by
+1
thanks a lot ..:-)
0
can we do if else using regular grammar??
0
No we cannot .. As regular languages have limited power as compared to CFLs
0
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 (14.2k points)
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
50,654 questions
56,169 answers
193,876 comments
94,298 users