The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
20 views
Suppose I have given a problem and I need to prove that problem to be regular or say CFL then is it a wrong approach that if I reduce a problem to a CFL or non CFL and claim that the original language is also CFL or non CFL respectively ?

According to me it's wrong approach because say I reduce a problem to a non CFL then it implies that the original problem may be non CFL but doesn't guarantee to be non CFL.

Right??
asked ago in Theory of Computation by Active (3.9k points) | 20 views
0
Please give an example to make the understanding easier...i am losing track of your statement by the time i reach the end..
0
Say for Example i have   L = { a^i b^j c^j | i,j >= 1 }

Well see this is CFL but lets say its not.   If i put i = j which i can according to the constraint, then it will become same language as  L = { a^nb^nc^n | n>= 1} which is not CFL. Then i can't claim that the above L is not CFL as it may be a CFL.

I just want to be sure that my thinking is right or not !

Please log in or register to answer this question.



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

36,995 questions
44,571 answers
126,775 comments
43,637 users