281 views
1 votes
1 votes
If s is a string over (0+1)*. Which one of the following languages is not regular?

A. L = {s ϵ {0, 1}* | n0(s) is a 3-digit prime}

B. L = {s ϵ {0, 1}* | for every prefix s' of s, |n0(s')-n1(s')| <= 2}

C. L = {s ϵ {0, 1}* | |n0(s)-n1(s)| <= 4}

D. L = {s ϵ {0, 1}* | n0(s) mod 7 = n1(s) mod 5 = 0}

1 Answer

0 votes
0 votes
C is correct.

We need to maintain the count of 1's and 0's and the count is not finite.

while in option B we can choose some prefixes which is finite and decide whether the length is <= 2 or not.

Related questions

0 votes
0 votes
1 answer
1
practicalmetal asked Mar 25, 2023
374 views
The solution to $X = r +Xs$ by Arden’s Lemma when s has ϵa) an infinite number of solutionsb) a finite number of solutionsc) is always uniqued) none
1 votes
1 votes
1 answer
2
atulcse asked Jan 28, 2022
460 views
Which of the following languages is/are regular?
5 votes
5 votes
3 answers
3
Hirak asked May 25, 2019
1,729 views
Consider the following statements:$S_1:\{(a^n)^m|n\leq m\geq0\}$$S_2:\{a^nb^n|n\geq 1\} \cup \{a^nb^m|n \geq1,m \geq 1\} $Which of the following is regular?$S_1$ only$S_2...