Log In
3 votes

Can anyone explain each option in detail. I am unable to get this property. .!!

in Theory of Computation 2.4k views

1 Answer

15 votes
Let L={0,10,110,1111} . this language satisfies the prefix property since a string in this language will not act as prefix for other strings in this language. Consider another language L1={01,11,110,011}. In this language 01 is acting as a prefix for 011 and 11 is acting as a prefix for 110. Therefore this is not a language satisfying prefix property.

Just have a look at option d.

Language contains strings over (0+1)* where number of 0's = number of 1's

consider 2 strings 01,0110 in the language. 01 is a prefix for 0110. So this language does not satisfy prefix property.

Other three languages satisfy prefix property.
Thnku for this explanation.. I got it now.
i think $B$ too will not followprefix property because $B=(a+b)^{*}$
I think you are considering x as (0+1)* . x is just one character here.

Related questions

0 votes
1 answer
Set of languages accepted by DPDA by empty stack contain only those DCFL's with prefix property. and DPDA with empty stack doesnt accept any regular language too becaust it doesn't satisfy prefix property. can anyone explain this with the help of PDA ? Just take example of regular ... n >= 0 } or any language which doesn't prefix property. I just want to know where it will get stuck on PDA.
asked Jul 25, 2018 in Theory of Computation daksirp 702 views
3 votes
2 answers
what is prefix property ?
asked Dec 22, 2017 in Theory of Computation Raveena Yadav 1 356 views
8 votes
1 answer
How to find DPDA’s that accept by null stack? Someone explain the prefix property for DPDA,How can we use this property?
asked Nov 2, 2017 in Theory of Computation set2018 1.3k views