Register

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

• edited by
295 views
0 votes
0 votes

For strings $w4 and $t,4 write $w \circeq t$ if the symbols of $w$ are a permutation of  the symbols of $t.$ In other words, $w \circeq t$ if $t$ and $w4 have the same symbols in the same quantities, but possibly in a different order.

For any string $w,$ define $SCRAMBLE(w) = \{t \mid t \circeq w\}.$ For any language $A,$ let $SCRAMBLE(A) = \{t \mid t in  SCRAMBLE(w) \text{for some}  w\in A\}$.

  1. Show that if $\Sigma = \{0,1\}$, then the SCRAMBLE of a regular language is context free.
  2. What happens in part $(a)$ if $\Sigma$ contains three or more symbols? Prove your answer.
• edited 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
2
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
1 votes
1 votes
1 answer
3
admin asked May 4, 2019
1,711 views
Michael Sipser Edition 3 Exercise 2 Question 36 (Page No. 158)
Give an example of a language that is not context free but that acts like a $CFL$ in the pumping lemma$.$ Prove that your example works$.$ $\text{(See the analogous example for regular languages in Question 54.)}$
Give an example of a language that is not context free but that acts like a $CFL$ in the pumping lemma$.$ Prove that your example works$.$ $\text{(See the analogous examp...
User Avatar
0 votes
0 votes
0 answers
4
admin asked Oct 12, 2019
421 views
Michael Sipser Edition 3 Exercise 2 Question 46 (Page No. 158)
Consider the following CFG $G:$ $S \rightarrow SS \mid T$ $T \rightarrow aT b \mid ab$ Describe $L(G)$ and show that $G$ is ambiguous. Give an unambiguous grammar $H$ where $L(H) = L(G)$ and sketch a proof that $H$ is unambiguous.
Consider the following CFG $G:$$S \rightarrow SS \mid T$$T \rightarrow aT b \mid ab$Describe $L(G)$ and show that $G$ is ambiguous. Give an unambiguous grammar $H$ where ...
User Avatar
Link Copied!