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

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!