# Tagged Questions

39 views

### Basic Question about ambiguity of Grammar

I saw one book in Computation Course. I take a picture from this book, and in this book say why (or not) the following grammar is ambiguous? I couldn't find any solution to prove it's ambiguous. ...
34 views

### Language of a grammar vs regular expression vs nfa

I read some note about Automaton Course. i see this note, that following all is the same. but i think the L(g) is not equal to NFA and regular expression. anyone could help me with defining the ...
31 views

### Pushdown Automata and Challenge in Grammar

I read one old-midterm exam on Automata. consider: the language that accepted by above pushdown automata is not generated by which of the following grammar? 1) S->aBaa|a$\epsilon$ ...
14 views

### Can this language be solved in PTIME?

I would like to know why we cannot prove that $P \subsetneq PSPACE$ by considering the following language for some particular Turing Machine $M$: $L_M:=$ {$w : M$ accepts or rejects $w$ without using ...
176 views

### The mother of all undecidable problems

It is usual to show that a problem P is undecidable by showing that the halting problem reduces to P. Is it the case that the halting problem is the mother of all undecidable problems in the sense ...
72 views

### $NP^{PP} vs. PP^{NP}$, which one subsumes the other?

I understand why P with an NP oracle ($P^{NP}$) subsumes $NP$: because it contains co-NP. But how about NP with a P oracle? Can it be any different from NP? (I'm guessing they are the same otherwise ...
63 views

### TAUTOLOGIES NP-Complete Condition

The decision problem TAUTOLOGIES is, Given $\forall x_1 \forall x_2 ... \forall x_n$ $\phi(x_1, x_2, ... x_n)$ a set of universally quantified Boolean variables and a Boolean formula ...
46 views

### Recursive Set and Complement Problem

if we have $$A=\{x:|W_x\ne\phi\}$$ can we say always my tight listed below is true? $A$ is recursive , $A$ is r.e, complement of $A$ is r.e, complement of $A$ is not recursive?
12 views

### Proof of theorem about connection between nondeterministic and deterministic Turing machines complexity classes

I need source for proof of this theorem: Every $T(n)$ time nondeterministic Turing machine has an equivalent $2^{O(T(n))}$ deterministic Turing machine. I have book by Michel Sipser, ...
36 views

### Languages in P that are not P-complete

Why aren't there any languages in P that are not P-complete?
61 views

### Prove that RE is closed under reduction

Prove that the class RE is closed under reduction. Definitions: A language $A \subseteq \Sigma^*$ is called reducible to $B \subseteq \Gamma^*$ ( denoted by $A \leq B$) if there is a computable ...
67 views

### Primitive recursive and Turing machines

Can someone give me a hint or the start of a possible proof for the following theorem: A function $f: \mathbb{N}^r \rightarrow \mathbb{N}$ is primitive recursive if and only if there is a ...
46 views

### Turing machines and tape complexity

Are the following statements true and/or false? There is a total function $g: \mathbb{N} \rightarrow \mathbb{N}$ so that for each Turing machine $M$ and each natural number $t$ we have: (*) ...
110 views

### Why do complex grammars require powerful algorithms?

I am reading a fabulous book on Formal Languages and in the book it says: As the rewrite rules of a grammar become more complex, the algorithm for recognizing the associated language becomes ...
75 views

### Unknown symbol '#' in set

I am reading a text on Complexity theory. There is a set whose notation I cannot understand: "Let $\sum$ = {0,1,#}" From the context, and given that the book is used computer science courses, it ...
91 views

### Simulating an alternating Turing Machine

I'm trying to figure out this question: Let's say we have an alternating Turing Machine that makes a restricted number of alternations (i.e. switches from a universal to an existential state or vice ...