289 views
0 votes
0 votes

A string $y$ is said to be a permutation of the string $x$ if the symbols of $y$ can be reordered to make $x.$ For instance, the permutations of string $x=011$ are $110,101,$ and $011.$ If $L$ is a language then $\text{perm(L)}$ is the set of strings that are permutations of strings in $L.$ For example, if $L=\{0^{n}1^{n}|n\geq 1\},$ then $\text{perm(L)}$ is the set of strings with equal numbers of $0's$  and $1's.$

  1. Give an example of a regular language $L$ over alphabet $\{0,1\}$ such that $\text{perm(L)}$ is not regular.Justify your answer. Hint$:$ Try to fi nd a regular language whose permutations are all strings with an equal number of $0's$ and $1's.$
  2. Give an example of a regular language $L$ over alphabet $\{0,1,2\}$ such that $\text{perm(L)}$ is not context-free.
  3. Prove that for every regular language $L$ over a two-symbol alphabet , $\text{perm(L)}$ is context-free.

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
1
admin asked Apr 11, 2019
138 views
Give the formal proof of theorem $7.25:$ that the $CFL's$ are closed under reversal.
0 votes
0 votes
0 answers
3
admin asked Apr 11, 2019
307 views
Modify the $CYK$ algorithm to report the number of distinct parse trees for the given input, rather than just reporting membership in the language$.$
0 votes
0 votes
0 answers
4