The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
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.

asked in Theory of Computation by Loyal (8.5k points) | 28 views
Please give an example to make the understanding easier...i am losing track of your statement by the time i reach the end..
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
47,894 questions
52,260 answers
67,679 users