Question: he operation Perm(w), applied to a string w, is all strings that can be constructed by permuting the symbols of w in any order. For
| he operation Perm(w), applied to a string w, is all strings that can be constructed by permuting the symbols of w in any order. For example, if w = 101, then Perm(w) is all strings with two 1's and one 0, i.e., Perm(w) = {101, 110, 011}. If L is a regular language, then Perm(L) is the union of Perm(w) taken over all w in L. For example, if L is the language L(0*1*), then Perm(L) is all strings of 0's and 1's, i.e., L((0+1)*). If L is regular, Perm(L) is sometimes regular, sometimes context-free but not regular, and sometimes not even context-free. Consider each of the following regular expressions R below, and decide whether Perm(L(R)) is regular, context-free, or neither:
(01)* 0*+1* (012)* (01+2)* |
| a) | Perm(L(0*+1*)) is regular. | ||
| b) | Perm(L((01)*)) is regular. | ||
| c) | Perm(L((01)*)) is not context-free. | ||
| d) | Perm(L((01+2)*)) is regular. |
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
