edited by
397 views
0 votes
0 votes

For $\text{A, B} \subseteq \Sigma^*,$  define

$A/B = \{x \in \Sigma^* | \exists y \in  B , xy \in A \}$

If L is a CFL and R is regular, then L/R is

  1. Regular
  2. CFL but not regular
  3. Recursive but not CFL
  4. None of the above

To solve this problem I am trying in this way –

Let us consider that $L$ is $a^nb^n$ and $R$ is $b^*$,

$A/B = \frac{a^nb^n}{b^*} \\= \frac{a^nb^n}{ \{\epsilon , b, b^2 , \dots \}} \\ = \{a^nb^n, a^nb^{n-1}, a^nb^{n-2} , \dots\}$

So it contains strings like $a^nb^n, a^nb^{n-1}, \dots $ which we know that are not regular but they are CFL.

Hence, $L/R$ is CFL but not Regular.

Please advise me that am I thinking in correct way or not?

 

edited by

Please log in or register to answer this question.

Related questions

1 votes
1 votes
1 answer
1
Na462 asked Sep 11, 2018
1,550 views
Is Language L = {0(n+m) 1(k+l) | m = l, and m,n,k,l ≥ 1 } a regular language ? explain
1 votes
1 votes
1 answer
2
ankitgupta.1729 asked Feb 24, 2018
282 views
Under Which class of language , Set of binary strings represents Fibonacci Sequence over input alphabet {0,1} ? I think either it is Context Sensitive Language or Recursi...
0 votes
0 votes
1 answer
3
srestha asked May 24, 2018
754 views
Is it regular?$\left \{ \left ( 0^{n} \right )^{m}|n<m,n,m\geq 1 \right \}$