# Are questions on introductory undergraduate CS theory appropriate here?

This is my first time to be involved in a site beta, and I would like to gauge the community's opinion on this subject.

On StackOverflow (and possibly Math.SE), questions on introductory formal language and automata theory pop up... questions along the lines of "How do I show language L is/isn't regular?", "How do I show language L is/isn't context-free?", "How do you convert a NFA to a DFA?", etc. I assume that questions such as these are unambiguously on-topic here; please correct me if I am mistaken.

Other questions, such as "How do I get a regular expression (regular grammar, context-free grammar, context-sensitive grammar, unrestricted grammar, DFA, NFA, PDA, LBA, TM, etc.) for language L?", are probably also appropriate here, although I suppose these could be construed as programming questions (in a sense, it's sort of equivalent) and therefore more appropriate for StackOverflow. What are the thoughts on this? I feel like this community would be better suited to providing correct and complete answers to such questions.

What about questions regrding normalizing relations in relational database theory? What about questions on proving loop invariants, or asymptotic bounds by induction? EDIT: What about questions from operating systems, such as on the optimality of scheduling policies, dining philosophers, etc.? What about questions from computer architecture, networks, parallel computing, etc. that don't involve programming and don't involve hardware? Perhaps even more interestingly, what about questions on the syntax and semantics of specific real programming languages (i.e., what does the following C code do, and why does it do that? Something from an introductory course on programming language theory). EDIT: For instance, what about the following question, from a CS GRE?

Consider the following Pascal-like program fragment:

var i, j : integer;
procedure P(k, m : integer) ;
begin
k := k - m;
m := k + m;
k := m - k;
end;
i := 2;
j := 3;
P(i, j);


If both parameters to P are passed by reference, what are the values of i and j at the end of the program fragment?

EDIT: Now that I look at the kind of questions I had in mind, I feel like they're more likely to be questions with pseudocode... if the syntax matches that of a particular language, it's probably just a pseudocode convention adopted by the authors. As such, questions specific to real capabilities of real languages are probably not appropriate...

My gut feeling is that all of this should be unambiguously on-topic, with the caveats associated with "homework" questions. I thought I would ask, however, since a lot of that is being asked on StackOverflow and Math.SE.

Personally I'd like for this site to be as inclusive as possible (or at least pretty inclusive). Overlap with existing sites isn't necessarily a problem. Just because a question would be on topic somewhere else it doesn't necessarily have to be off topic here.

So I'd answer "yes" to all of those, except possibly the last one:

what does the following C code do, and why does it do that? Something from an introductory course on programming language theory

I'm not quite sure what you have in mind here. "What does this C code do?" sounds more like a question I'd expect in "Introduction to Programming" (the contents of which I'd say should not belong here - we don't want to be a superset of Stack Overflow), not "Introduction to Programming Language Theory". Unless the question is supposed to be answered using a previously introduced formal semantics of C, in which case I'd accept it here.

• I agree completely. The only addition is an obvious remark: the questions should be well-posed, that is the questioner should demonstrate involvement and effort, and should state their question clearly using established notation. – Raphael Mar 7 '12 at 16:51

Of course they should be on topic. Graduate level questions go on TCS, what would it leave us if we didn't take undergrad questions (even just "introductory" ones)? And "introductory" is rather ambiguous.

• Graduate level TCS questions go to CSTheory. But there's plenty of computer science that isn't theory. – Dave Clarke May 19 '12 at 18:51