Consider the following languages-1- A - wwrwrw - w- -2-B- wwrxxr-w-x- -3- C-aibjakbl-i-j-k-l- 0-i-j-k-lThe number of the above languges which is CFL-s is-are -

Only B and C are CFLs. In language C, Push and Pop is clear means Input a, Tos S |a| a→ Push x Input b, Tos S |a| b → Push x Input b, Tos S |a| b → Po ...

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

Byju's Answer

Other

Introduction to CFL

Consider the ...

Question

Consider the following languages;
$1. A = w w^{r} w^{r} w | w \in Σ^{}$
$2. B = {w w^{r} x x^{r} | w, x \in Σ^{}}$
$3. C = a^{i} b^{j} a^{k} b^{l} | = | i, j, k, l \geq 0, (i + j) = (k + l)$

The number of the above languges which is CFL's is/are ____.

Open in App

Solution

Only B and C are CFLs.

In language C, Push and Pop is clear means

- Input a, Tos S |a| a $\to$ Push x
- Input b, Tos S |a| b $\to$ Push x
- Input b, Tos S |a| b $\to$ Pop x
- Input a, Tos S |a| b $\to$ Pop x
- Input completed, Tos S $\to$ String accepted

Language B, can be broken down as ww and xx an

Let $L_{1}$ = ww (CFL
$L_{2}$ = xx (CFL)
Thus, F is CFI since B = $L_{1}$ , $L_{2}$ and contexts free language

Suggest Corrections

Similar questions

Q. Consider the following languages.

L_{1} =

{

a^{i} b^{j} c^{k} | i = j, k \geq 1

}

L_{2} =

{

a^{i} b^{j} | j = 2 i, i \geq 0

}
Which of the following is true?

Q. Which of the following are CFLs?

A = {x w x^{r} | x, w \in Σ^{*}, | x | = | w |}

B = {x $ w | w i s a s u b s t r i n g o f x, x \in Σ^{*}, $ \in Σ}

Q. Consider the following C-function in which a [n] and b [m] are two sorted integer arrays and c [n+m] be another integer array.

void xyz (int a[ ], int b[ ], int c[ ])
{
int i, j, k;
i = j = k = 0;
while ((i < n) && (j < m))
if (a[i] < b[j])
c[k++] = a[i ++];
else
c[k++] = b[j ++];
}

Which of the following condition(s) hold after the termination of the while loop?

(i) j < m, k = n + j - 1 & a[n- 1] < b[j] if i = n
(ii) i < n, k = m + i - 1 & b[m- 1]

\leq

a[i] if j = m

Q. Consider the following C function.
int fun1 (int n)
{
int i, j, k, p, q = 0;
for (i = 1; i < n; + + i)
{
p = 0;
for (i = n; j > 1; j = j/2)
++p;
for (k = l; k < p; k = k*2)
+ + q:
} return q;
}
Which one of the following most closely approximates the return value of the function fun1?

Q. Let L =

L_{1} \cap L_{2}

, where

L_{1} a n d L_{2}

are languages as defined below:

L_{1}

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

}

L_{2}

a^{i} b^{j} c^{k} | i, j, k \geq 0

}
Then L is

Join BYJU'S Learning Program

Consider the following languages; 1.A=wwrwrw|w∈Σ∗ 2.B={wwrxxr|w,x∈Σ∗} 3.C=aibjakbl|=|i,j,k,l≥0,(i+j)=(k+l) The number of the above languges which is CFL's is/are ____.

Consider the following languages;
$1. A = w w^{r} w^{r} w | w \in Σ^{}$
$2. B = {w w^{r} x x^{r} | w, x \in Σ^{}}$
$3. C = a^{i} b^{j} a^{k} b^{l} | = | i, j, k, l \geq 0, (i + j) = (k + l)$

The number of the above languges which is CFL's is/are ____.