The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
14 views
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 ago in Theory of Computation by (59 points) | 14 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 ago by Boss (16.6k points)


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,781 comments
43,637 users