Tagged Questions
3
votes
2answers
40 views
If $L\in REG$ then $M$ has a finite number of distinct rows
Let $L \subseteq \Sigma^{\star}$ and let $M^{\Sigma^{\star} \times \Sigma^{\star}}(\{0,1\})$ an infinite matrix such that for each $x,y\in \Sigma^\star$:
$$
m_{x,y}=\begin{cases}
1 & x y\in L\\
0 ...
1
vote
1answer
353 views
Language that is recursively enumerable, but not recursive
I have a problem with this task:
Show that this language is recursive enumerable, but not recursive: $L = \{ w \in \{0,1\}^* | M_w(x)\; \text{converges for some input}\; x \}$ (where $M$ is turing ...
3
votes
1answer
141 views
Proving Turing Completeness by Simulating Rule 110
Something I've heard often is that Rule 110 is the `simplest' Turing-complete formalism. As a programming exercise in a language I am new to, I implemented a function that computes from an initial ...
7
votes
1answer
157 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
103 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 ...
8
votes
2answers
213 views
Why is it undecidable whether two finite-state transducers are equivalent?
According to the Wikipedia page on finite-state transducers, it is undecidable whether two finite-state transducers are equivalent. I find this result striking, since it is decidable whether two ...
3
votes
3answers
455 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, ...
