patternMinor
Given L is a regular language, prove that Perm(L) is Context-Free
Viewed 0 times
permfreeregularlanguageprovethatcontextgiven
Problem
Given a regular language $L$ defined over $\Sigma = \{0, 1\}$. We define a new language $$Perm(L) = \{w \mid \exists x \in L, w \in perm(x)\}, $$ where $perm(x)$ is the set of all permutations of the word $x$.
We have to show that $Perm(L)$ is context-free.
I have looked at the properties that neither CFL nor Regular languages are closed under permutation. Also, the problem comes with the following hint.
Hint: Build a PDA for $perm(L)$ which guesses a permutation of the input string and runs the DFA for $L$ on it, and uses the stack to check that it indeed guessed a valid permutation of the input string. The fact that the alphabet has only two symbols will be crucial for the latter check.
I am unable to use this hint to proceed further. Any help is appreciated!
We have to show that $Perm(L)$ is context-free.
I have looked at the properties that neither CFL nor Regular languages are closed under permutation. Also, the problem comes with the following hint.
Hint: Build a PDA for $perm(L)$ which guesses a permutation of the input string and runs the DFA for $L$ on it, and uses the stack to check that it indeed guessed a valid permutation of the input string. The fact that the alphabet has only two symbols will be crucial for the latter check.
I am unable to use this hint to proceed further. Any help is appreciated!
Solution
Clearly we cannot keep both the number of $a$'s and the number of $b$'s on the stack, because what order should we use. The solution (I think) is to keep the difference of these numbers on the stack. Or better, the difference between the promised numbers in the DFA computation on word $x\in L$ that we guess, and those that are realised by the (permuted) word $w$ that we read.
The stack is used to count this difference (and we must be able to store both positive and negative numbers).
In each step of the computation (i) we read a symbol $a$ from the tape and (ii) randomly follow a letter $b$ in the DFA for $L$. If these letters match then we comtinue. If these letters differ we increase or decrease the number of symbols on the stack: say we increase that number if $a=0$ and decrease if $a=1$.
We accept if the simulated computation on the DFA ends in an accepting state ánd the stack is empty (or better represents the number zero).
PS. This might look different from Yuval's solution, but it basically the same.)
The stack is used to count this difference (and we must be able to store both positive and negative numbers).
In each step of the computation (i) we read a symbol $a$ from the tape and (ii) randomly follow a letter $b$ in the DFA for $L$. If these letters match then we comtinue. If these letters differ we increase or decrease the number of symbols on the stack: say we increase that number if $a=0$ and decrease if $a=1$.
We accept if the simulated computation on the DFA ends in an accepting state ánd the stack is empty (or better represents the number zero).
PS. This might look different from Yuval's solution, but it basically the same.)
Context
StackExchange Computer Science Q#138357, answer score: 6
Revisions (0)
No revisions yet.