Notices
Results 1 to 5 of 5

Thread: Theory of Computation HELP NEEDED

  1. #1 Theory of Computation HELP NEEDED 
    New Member
    Join Date
    Feb 2009
    Location
    nashville
    Posts
    3
    Show that the language of all C++ valid identities (variable or function names) is regular


    Goody
    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Freshman
    Join Date
    Mar 2009
    Location
    Great Barrington
    Posts
    62
    Can you elaborate? I'm afraid I don't understand.


    Reply With Quote  
     

  4. #3  
    New Member
    Join Date
    Apr 2009
    Posts
    2
    Might I suggest that this thread become a sticky?

    For the C++ valid identities question... I think you could construct the following simple DFA:

    let the start state be a reject state, qs.

    for all transitions from the start state that are valid first characters of a function or a variable advance to a loop state, ql.

    if the first character of a function or variable name is invalid advance to a reject state, qr.

    while in ql, for all valid characters loop into ql. If an invalid character is encountered, advance to qr.

    This DFA should decide whether or not a C++ function or variable is a valid identity. Since the language is decided by a DFA, the language is regular. If you need to see a picture of the construction of the DFA, let me know and I will try to post a photo.

    On another Theory question, Could someone tell me why the following proof is wrong?

    Prove that the language

    Acfg = {<G,w> | G is a CFG such that w is an element of L(G)}

    is decidable.

    Proof:
    "On input <G,w>
    1) Convert G to Chomsky Normal Form
    2) For each symbol, s, in w
    __3) For each rule, A->s, in G
    ____4) Mark the variable A
    __5) If no variable was marked, REJECT
    6) For each pair of marked variables, B and C
    __7) For each rule A->BC
    ____8) Mark the variable A
    9) If the start symbol is marked, ACCEPT, else, REJECT.

    I would like someone to explain to me why this does not decide if a string w is in the language L(G). The machine marks the start symbol if and only if there is a derivation tree that generates the input string w.

    PS: Since some browsers eliminate multiple whitespace characters, I used _ to show the loop nesting.
    Reply With Quote  
     

  5. #4  
    Universal Mind John Galt's Avatar
    Join Date
    Jul 2005
    Posts
    14,168
    Quote Originally Posted by jungledrew64
    Might I suggest that this thread become a sticky?
    Might I suggest we don't do people's homework for them.
    Reply With Quote  
     

  6. #5  
    New Member
    Join Date
    Apr 2009
    Posts
    2
    The question I posed is not a homework problem. It was marked wrong on an exam, and I don't think that it is wrong. As far as the first post goes, my "proof" was very informal and probably not exactly the answer the question was looking for. Given the overview one might be able to formulate a nice formal proof or at least come to a better understanding of the problem at hand.

    I suggested that this be a sticky, because there are very few message boards where people can better understand the Theory behind computer science, however Theoretical Mathematics questions/proofs are given all over the internet. It would be nice if Theoretical Computer Science had similar forums. The only way to grasp a better understanding of this material is to study examples and the logic that they apply. By answering a few of these questions and explaining the proofs behind them; we can lead others to a better understanding of our science. And more people understanding our science, yields more questions being asked and more solutions being found. This is how mathematics has been so successful in pushing the boundaries of it's own science. Mathematicians trust that people are responsible enough to stray from cheating and would rather you come to a complete understanding of the material. And I believe this mentality could be helpful to the field of computer science.
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •