The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
40 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 in Theory of Computation by (133 points) | 40 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 (20.7k points)

Related questions



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

44,237 questions
49,719 answers
163,889 comments
65,834 users