93 views
2 2 votes

Let $\text{COPY}=\{ww\mid w\in\{a,b\}^*\}$ and $\text{NOTCOPY}=\{x\in\{a,b\}^*\mid x\text{ is not of the form }ww\}$.

Which statements are correct?

  1. $\text{COPY}$ is not CFL.
     
  2. $\text{NOTCOPY}$ is CFL.
     
  3. Since $\text{COPY}$ is not CFL, $\text{NOTCOPY}$ must also be not CFL.
     
  4. Every odd-length string belongs to $\text{NOTCOPY}$.
     
  5. For an even-length string not of the form $ww$, there is some position where the first half and second half differ.

1 Answer

1 1 vote

Let $\text{COPY}=\{ww\mid w\in\{a,b\}^*\}$ and $\text{NOTCOPY}=\{x\in\{a,b\}^*\mid x\text{ is not of the form }ww\}$.

A. True

$\text{COPY}$ is a standard example of a language that is not context-free.

A PDA with one stack cannot store an arbitrary first half $w$ and then compare the second half with it in the same order.

Hence, $\text{COPY}\notin$ CFL.

B. True

$\text{NOTCOPY}$ is context-free.

There are two possibilities for a string to be in $\text{NOTCOPY}$:

  • Its length is odd.

  • Its length is even, but the first half and second half differ at some position.

An NPDA can nondeterministically guess a position where the two halves differ and verify the required length relationship using its stack.

Hence, $\text{NOTCOPY}\in$ CFL.

C. False

From $\text{COPY}\notin$ CFL we cannot conclude that its complement is also not CFL.

CFLs are not closed under complement.

In this particular case, $\text{COPY}\notin$ CFL but $\text{NOTCOPY}\in$ CFL.

D. True

Every string of the form $ww$ has length $|ww|=2|w|$, which is always even.

Therefore, every odd-length string cannot be of the form $ww$.

So every odd-length string belongs to $\text{NOTCOPY}$.

E. True

Suppose a string has even length $2n$.

Split it into two equal halves:

$x=uv$, where $|u|=|v|=n$.

If $x$ is not of the form $ww$, then $u\neq v$.

Therefore, there must be at least one position $i$ such that the $i$-th symbol of $u$ differs from the $i$-th symbol of $v$.

Hence statement E is true.

 

Answer:
Position:
Show:

Related questions

2 2 votes
1 1 answer
120
120 views
GO Classes asked Sep 18
120 views
Let $P=\{a^n\mid n\text{ is prime}\}$.Which statements are correct?$P$ is regular. $P$ is CFL but not regular. If $P$ were CFL, then because it is unary, it would have to...
2 2 votes
1 1 answer
81
81 views
GO Classes asked Sep 18
81 views
Let $A=\{w\in\{a,b,c\}^*\mid \#a(w)=\#b(w)=\#c(w)\}$ and let $R=a^*b^*c^*$. Which statements are correct?$R$ is regular. If $A$ were CFL, then $A\cap R$ would be CFL. $A\...
2 2 votes
1 1 answer
73
73 views
GO Classes asked Sep 18
73 views
Consider the following languages:$L_1=\{w\in\{a,b\}^*\mid \#a(w)=\#b(w)\}$$L_2=\{w\in\{a,b,c\}^*\mid \#a(w)=\#b(w)=\#c(w)\}$$L_3=\{a^m b^n\mid 5m+4n=44,\ m,n\ge0\}$Which ...
1 1 vote
1 1 answer
66
66 views
GO Classes asked Sep 18
66 views
Let $B=\{0^n\#0^{2n}\#0^{3n}\mid n\ge0\}$.Which statements are correct for proving $B$ is not CFL using the pumping lemma?Choose $s=0^p\#0^{2p}\#0^{3p}$, where $p$ is the...