Linear probing is a simple dynamic dictionary.
The dictionary is represented by an array A of length $m = 2n$.
To insert an element $x$, one tries to place it into A at location $h(x)$, where $h$ is some random function. If that cell is occupied, then one moves to the right until one finds the fi...
Assume we apply the following operation on the regular language $L$:
$$OP(L)=\{a_2a_1a_4a_3\dots a_{2n}a_{2n-1}:a_1a_2a_3\dots a_{2n}\in L\}$$
Why $OP(L)$ remains regular?
I think this is as the same as shuffle but I have no idea to show that.
Assume we apply the following operation on the regular language $L$:
$$OP(L)=\{a_2a_1a_4a_3\dots a_{2n}a_{2n-1}:a_1a_2a_3\dots a_{2n}\in L\}$$
Why $OP(L)$ remains regular?
I think this is as the same as shuffle but I have no idea to show that.
