The Gateway to Computer Science Excellence
+3 votes

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

in Theory of Computation by Active (2.8k points) | 2.1k views

1 Answer

+14 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.
by Active (1.5k points)
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.
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,737 questions
57,291 answers
104,901 users