Register

Michael Sipser Edition 3 Exercise 2 Question 39 (Page No. 158)

• retagged by
257 views
0 votes
0 votes
For the definition of the shuffle operation. For languages $A$ and $B,$ let the $\text{shuffle}$ of $A$ and $B$ be the  language $\{w| w = a_{1}b_{1} \ldots a_{k}b_{k},$ where  $ a_{1} · · · a_{k} ∈ A $ and $b_{1} · · · b_{k} ∈ B,$ each $a_{i}, b_{i} ∈ Σ^{*}\}.$

Show that the class of context-free languages is not closed under shuffle.
• retagged by
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
admin asked Oct 12, 2019
244 views
Michael Sipser Edition 3 Exercise 2 Question 45 (Page No. 158)
Let $A = \{wtw^{R}\mid w,t\in\{0,1\}^{\ast}\:\text{and} \mid w \mid = \mid t \mid \}$. Prove that $A$ is not a CFL.
Let $A = \{wtw^{R}\mid w,t\in\{0,1\}^{\ast}\:\text{and} \mid w \mid = \mid t \mid \}$. Prove that $A$ is not a CFL.
User Avatar
0 votes
0 votes
0 answers
3
admin asked Oct 12, 2019
167 views
Michael Sipser Edition 3 Exercise 2 Question 42 (Page No. 158)
Let $Y = \{w\mid w = t_{1}\#t_{2}\#\dots t_{k} \:\text{for}\: k\geq 0,\text{each}\: t_{i}\in 1^{\ast}, \text{and}\: t_{i}\neq t_{j} \text{whenever}\: i\neq j\}$.Here $\Sigma = \{1,\#\}$. Prove that $Y$ is not context free.
Let $Y = \{w\mid w = t_{1}\#t_{2}\#\dots t_{k} \:\text{for}\: k\geq 0,\text{each}\: t_{i}\in 1^{\ast}, \text{and}\: t_{i}\neq t_{j} \text{whenever}\: i\neq j\}$.Here $\Si...
User Avatar
0 votes
0 votes
0 answers
4
admin asked Oct 12, 2019
258 views
Michael Sipser Edition 3 Exercise 2 Question 41 (Page No. 158)
Read the definitions of NOPREFIX(A) and NOEXTEND(A) in Question $1.40$. Show that the class of CFLs is not closed under NOPREFIX. Show that the class of CFLs is not closed under NOEXTEND.
Read the definitions of NOPREFIX(A) and NOEXTEND(A) in Question $1.40$.Show that the class of CFLs is not closed under NOPREFIX.Show that the class of CFLs is not closed ...
User Avatar
Link Copied!