Which of the following are regular sets-1- anb2m- n- 0-m- 0 2- anbm- n-2m 3- anbm- n- m 4- xcy- x-y- a- b -

1. { a^nb^2m| n≥ 0,m≥ 0 } is regular, since we can write L as a regular expression a^*(bb)^*. 2. nbsp;{ a^nb^m| n=2m } is a DCFL, but not regular since here, ...

You visited us 1 times! Enjoying our articles? Unlock Full Access!

Byju's Answer

Other

Objective Session 2

Which of the ...

Question

Which of the following are regular sets?

1. ${a^{n} b^{2 m} ∣ n \geq 0, m \geq 0}$

2. ${a^{n} b^{m} ∣ n = 2 m}$

3. ${a^{n} b^{m} ∣ n \neq m}$

4. ${x c y ∣ x, y ϵ {a, b}^{*}}$

Open in App

Solution

1. ${a^{n} b^{2 m} ∣ n \geq 0, m \geq 0}$ is regular, since we can write L as a regular expression $a^{} (b b)^{} .$

2. ${a^{n} b^{m} ∣ n = 2 m}$ is a DCFL, but not regular since here, we need to count the a's and compare with b's.

3. ${a^{n} b^{m} ∣ n \neq m}$ is same as ${a^{n} b^{m} ∣ n < m} \cup {a^{n} b^{m} ∣ n > m}$ each of which is a CFL and the union is also a CFL (Since CFLs are closed under union). However this language is not regular since we have to count a's and b's and compare them which cannot be done by a finite state machine.

4. ${x c y ∣ x, y ϵ {a, b}^{}}$ is regular since we can write a regular expression $(a + b)^{} c (a + b)^{*}$ for it.

Suggest Corrections

Similar questions

Q. Consider the following languages:

A = {a^{n} b^{m} | n, m \geq 0}

B = {a^{n} b^{m} | n \geq m \geq 0}

C = {a^{n} b^{m} | n = m \geq 0}

D = {a^{n} b^{m} | n \geq m \leq 100}

Which of the above are not regular?

Q. Which of the following languages is/are regular ?

L_{1} : {w x w^{R} ∣ w, x ϵ {a, b}^{*} a n d ∣ w ∣, ∣ x ∣> 0}

w^{R}

is the reverse of string w

L_{2} : {a^{n} b^{m} ∣ m \neq n a n d m, n \geq 0}

L_{3} : {a^{p} b^{q} c^{r} ∣ p, q, r \geq 0}

Q. Consider the following statements:

S_{1} : {0^{2 n} ∣ n \geq 1}

is a regular language

S_{2} : {0^{m} 1^{n} 0^{m + n} ∣ m \geq 1 a n d n \geq 1}

is a regular language

Which of the following is true about

S_{1} a n d S_{2}

Q. Let

l, m, n

be 3 regular expressions. Consider the following identities.

I . (l^{*} m^{*} n^{*})^{*} = (l m^{*} + m n^{*} + n l^{*})^{*} I I . (m n + m)^{*} m = m (n m + m)^{*} I I I . (l^{*} m^{*} n^{*})^{*} = (l^{*} + m^{*} n + n^{*})^{*} I V . (l^{*} m)^{*} = (l + m)^{*}

How many of the above identities are incorrect._________.

Q. Consider the following C program
main( )
{
int x, y, m, n;
scanf ('%d %d", &x, &y);
/* Assume x > 0 and y > 0*/
m = x; n = y;
while(m! = n)
{
if (m > n)
m = m-n;
else
n = n - m;
}
printf("% d", n);
}
The program computes

Join BYJU'S Learning Program

Which of the following are regular sets? 1. {anb2m∣n≥0,m≥0} 2. {anbm∣n=2m} 3. {anbm∣n≠m} 4. {xcy∣x,yϵ{a,b}∗}

Which of the following are regular sets?

1. ${a^{n} b^{2 m} ∣ n \geq 0, m \geq 0}$

2. ${a^{n} b^{m} ∣ n = 2 m}$

3. ${a^{n} b^{m} ∣ n \neq m}$

4. ${x c y ∣ x, y ϵ {a, b}^{*}}$