Thread: Theory of Computation HELP NEEDED

Show that the language of all C++ valid identities (variable or function names) is regular

Can you elaborate? I'm afraid I don't understand.

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.

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.

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.