1,088 views
0 votes
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

1 Answer

1 votes
1 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^* )^*$ .

Related questions

0 votes
0 votes
0 answers
2
jg662 asked Feb 22
67 views
Use the Pumping Lemma to show that the following languages over Σ={�,�}Σ={a,b} are not regular. In each case, carefully describe the string that will be pumped and ...