The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
Q.  Assertion (a): The language L= Set of all strings not containing 101 as a substring is regular set
Regular (r): L satisfies the regular set but not the pumping lemma.
A. Both (a) and (r) are true and (r) is a reason for (a)
B. Both (a) and (r) are true and (r) is not correct reason (a)
C. Both (a) and (r) are false
D. (a) is true but (r) is false
asked in Theory of Computation by (149 points) | 75 views

1 Answer

0 votes

Answer : D

The given language is Regular and Every regular language satisfies the Pumping lemma for Regular languages. So, $a$ is True and $r$ is false.



Simple RegEx for All strings not containing the substring 101:  $0^* (1^*000^* )^*1^* 0^*$ 

Notice that a $1$ may be followed by either a $1$ or by a $00$, and this pattern can be repeated as many times as we want. This pattern is expressed in $(1^*000^* )^* $. The extreme cases where a string can start or end with $0's$ or contain only $1's$ are covered by the expressions left and right from the pattern $(1^*000^* )^*$ .

answered by Boss (23.4k points)

Related questions

0 votes
0 answers
asked Jan 5 in Theory of Computation by Nandkishor3939 Active (1.2k points) | 30 views
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
48,449 questions
52,747 answers
68,219 users