1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Computer Science theory doubts

  1. Jan 24, 2014 #1
    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.

    1. The problem statement, all variables and given/known data
    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}

    3. 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.

    1. The problem statement, all variables and given/known data
    b) {wtw|w,t e {0,1}*}

    3. 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.

    1. The problem statement, all variables and given/known data
    2)Give an counter-example to show that the following contruction fails in to 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*

    3. 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

    1. The problem statement, all variables and given/known data
    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

    3. 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
     
    Last edited: Jan 24, 2014
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?



Similar Discussions: Computer Science theory doubts
  1. Engineering Science (Replies: 0)

  2. Materials Science (Replies: 0)

Loading...