1
vote
1answer
61 views

Countable Set & Formal Grammar

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. I try to summarize my though. I think the following proposition is true. suppose $\Sigma$ is arbitrary ...
8
votes
4answers
583 views

Why isn't there a pumping lemma for recursively enumerable languages?

I'm studying the theory of computation, and I know there are pumping lemmas for regular and context-free languages, but why not for recursively enumerable languages? Is there something about a Turing ...
1
vote
1answer
49 views

Is the language $L=\{ww^f|w\in \{0,1\}^*\}$ CFL?

Where $w^f=$flipping the bits of w. For example, $(0010)^f=1101$, $(010111)^f=101000$ I tried to prove that $L$ is not CFL using the pumping lemma, with no succeed. In addition, I need to prove ...
1
vote
3answers
70 views

How does one generally use partial function in logical statements?

How does one generally use partial function in logical statements? How it's done in practice? Specifically, let $M$ by a Turing machine, $f_M:\{0,1\}^*\to\{0,1\}$ the characteristic function which ...
1
vote
1answer
55 views

Undecidability of a Formal Language

I want to show that the following language is undecidable. Please help me verify the correctness of my solution. Thanks in advance! \begin{equation} ...
3
votes
1answer
36 views

Mapping reduction to show NeverHalt is undecidable

I need help with showing that $NeverHalt_{TM} = \{\langle M\rangle|M\text{ is a TM which runs forever on every input $w$}\}$ is undecidable by giving an explicit mapping reduction. To show that a ...
2
votes
1answer
221 views

Show that the language TOT={<M> | M is a Turing Machine that halts with all inputs} is not recursively enumerable nor its complement.

I've been thinking about how to show this but I'm stuck. I'm required to prove this: "Show that the language TOT={#M# | M is a Turing Machine that halts with all inputs} is not recursively ...
-2
votes
1answer
46 views

Probability over decidable languages

Let $\mathcal S$ be the set of all languages over some finite alphabet $\Sigma$. Prove that the probability of a randomly chosen (arbitrary distribution) language has a decider is zero.
1
vote
1answer
102 views

Proof of undecidability of $FINITE_{\text{TM}}$ and $USELESS_{\text{TM}}$

I came across these 2 problems about proving of undecidability of languages: $1$. $FINITE_{\text{TM}} = \{\langle M \rangle | M \text{ is a Turing machine and } L(M) \text{ is a finite language} \}$. ...
7
votes
5answers
425 views

A computer's memory is finite, so how can there be languages more powerful than regular?

A computer has a finite memory. There are no computers with infinite memory. Therefore the only languages that a computer can process are those whose member strings are finite. As I recall, the ...
3
votes
1answer
115 views

Explain why if the language A is recursive, then A is reducible to 0*1*

I'm in a theory of computation class and there is a problem that I think I am way overthinking. Can anyone point me in the right direction with the following: Give a short justification of the fact ...
2
votes
1answer
87 views

unary recursive language

I'm having trouble with this question: Given any language L is a subset of $\{0,1\}^*$, define the language $$\text{unary}(L) =\{0^{1x} | x \in L\}$$ The language $\text{unary}(L)$ is ...
0
votes
1answer
108 views

Unbounded number of tapes of Turing Machine

Turing Machine with multiple tapes can be encoded such that its computational power is equivalent to Turing Machine with single tape. My question is if we have unbounded number of tapes, just like the ...
7
votes
1answer
208 views

Does there exist a universal pushdown automaton?

Let $\Sigma$ be a fixed alphabet and let $PDA(\Sigma)$ be the set of all Push-Down-Automata (PDA's) having input alphabet $\Sigma$. Is there an alphabet $S$ and a function $f:PDA(\Sigma) \to S^∗$ such ...
2
votes
1answer
141 views

Is the set of codes of Deterministic Finite-State Automata a regular language?

Let $\Sigma$ be a given alphabet. Is there a way to code up Deterministic Finite state Automata (DFA) over $\Sigma$ as strings of $\Sigma$ in such a way that the corresponding subset of $\Sigma^*$ is ...
5
votes
1answer
218 views

Recursively enumerable languages are closed under the min(L) operation?

Define $\min(L)$, an operation over a language, as follows: $$ min(L) = \{ w \mid \nexists x \in L, y \in \Sigma^+ , w=xy \} $$ In words: all strings in language L that don't have a proper prefix in ...
6
votes
3answers
211 views

Reductions for regular languages?

To reason about whether a language is R, RE, or co-RE, we can use many-one reductions to show how the difficulty (R, RE, or co-RE-ness) of one language influences the difficulty of another. To reason ...
2
votes
1answer
239 views

Size bound on regular expression describing language of an $n$-state deterministic automaton

The class of languages that can be recognised by some deterministic finite automaton is the same as those described by some regular expression. I evoked this well-known fact in class when discussing ...
4
votes
2answers
270 views

A question on context-free languages from Sipser's computation book

I'm trying to learn some computability theory, and I came across a question in Sipser's book that I can't figure out. The exercise asks to show that there is an algorithm which will accept a ...
3
votes
3answers
706 views

Is the language of all strings over the alphabet “a,b,c” with the same number of substrings “ab” & “ba” regular?

Is the language of all strings over the alphabet "a,b,c" with the same number of substrings "ab" & "ba" regular? I believe the answer is NO, but it is hard to make a formal demonstration of it, ...