Computer Science theory doubts

[colt]

Hi, I would appreciate if someone can check my answers about three questions about computer science and if they are not, what it is missing.

Homework Statement

1)Proof that the following languages aren't regular. You can use the pumping lemma and the closing of the class of the regular languages under union, intersection and complement.

a) {w|w {0,1}* is not a palindrome}

The Attempt at a Solution

My solution: Pick up w as the string 010010. x=empty, y=01 & z=0010. By the pumping lemma the string xyyz should also be regular.
However xyyz=01010010 which is not a palindrome. So, by contradiction, letter a is not a regular language.

Homework Statement

b) {wtw|w,t e {0,1}*}

The Attempt at a Solution

My solution. Pick up w as the string 0101 and pick up t=011 as the other string. So wtw= 0101 011 0101 which belongs to {0,1}By the pumping lemma, the string xyyz should also be regular, However, choosing y=110 of 010 0|11 0|0101, the string 0101 011 110 0101 is produced which cannot be generated by wtw. So, by contradiction, letter b is not a regular language.

Homework Statement

2)Give an counter-example to show that the following contruction fails into proof that class of languages free of context is closed under the operation star. By A a language free of context that it is generated by the GLC G = {V,,R,S}. Add the new rule S -> SS e call the resulting grammar G'. That grammar is expected to generate a*

The Attempt at a Solution

I have only a superficial comprehension, I believe it is necessary that Rg', the set of production rules of G' must be equal to Rg united with {Sg'->SgSg'|e} or in another words Rg': Rg U {Sg'->SgSg'|e}. Even if that it is correct I don't understand why {Sg'->SgSg'|e} is necessary

Homework Statement

3)By A = {(R)|R it is a regular expression that describes a language containing at least a w string that has 111 as a substring (that it is, w=x111y to some x and some y)}. Show that A it is decidible

The Attempt at a Solution

Create a turing machine P, this machine receives a pair <R,W> where R is the regular expression in question and W is the set of all the strings of the form x111y. P converts R into a NFA called NFAR. It sends the pair <NFAR,W> to a TM N that acts as a subrotine of it. N will convert NFAR into a DFA called DFAR. Then inside this machine N, there is a turing machine M inside it, also acting as a subrotine. It sends the pair <DFAR,W> to M. When M receives its input, it will first determines whether it properly represents a DFA DFAR an a set of strings W. If not, it will reject, and as a result, so will N and then P. Otherwise, It will start to simulate DFAR over the first string w(i) of W (where i=0,1,2... n° last input string). If DFAR accepts, M halts in the accept state, and so will N and then P. Otherwise M will continue to looop through all the strings of W. If it reaches the last w(i) and it is not accepted, M will halt in the refect state and so will N and then P.

My fear is that the number of strings to be tested is infinite, so M could enter in a loop?

P.S: I just did a similar topic here http://www.mymathforum.com/viewtopic.php?f=27&t=45768

Thanks for any help

 

[Valkarie]

.My solution is correct, but you might want to add more detail about the specific steps of the Turing machine P and its subroutines N and M. For example, how does P convert R into a NFA? How does N convert NFAR into a DFA? How does M simulate DFAR over the first string w(i) of W? You should also mention that since there are only a finite number of strings in W, M cannot enter an infinite loop.