1
vote
3answers
27 views

Reducing a Decidability Problem to the Halting Problem

Let $L = \{(M, n): M$ halts on less than $n$ elements from a set S $\}$ I'm trying to come up with a generalization on how to solve these types of problems so I have not defined what S is. Since the ...
0
votes
3answers
58 views

the difference between regex operations (math) and regex (unix/linux)

what is the difference between regular expression operations (union, concatenation, kleene star) and regular expression (implemented in UNIX and can be used together with the grep command)? Are there ...
1
vote
2answers
45 views

Reduction between two languages and a common one

My question is as following : Let $A$ and $B$ be some languages, there exist a language $C$ such that $A\le C$ and $B\le C$, where "$\le$" means "reducible to", so $A\le C$ means there is a mapping ...
1
vote
0answers
78 views

Oracle Turing machine - $E_{\text{TM}}$ and $PCP$.

$$E_{\text{TM}}=\{\langle M\rangle|M\text{ is a TM and $L(M)=\emptyset$}\}.$$ $E_{\text{TM}}$ is undecidable $$PCP=\{\langle P\rangle|P\text{ is an instance of the Post Correspondence Problem with a ...
2
votes
1answer
32 views

Reducing A$_\text{TM}$ to REGULAR$_\text{TM}$

We can solve A$_\text{TM}$ problem using REGULAR$_\text{TM}$. Assume $R$ is a Turing machine that decides REGULAR$_\text{TM}$. We construct $S$ to decide A$_\text{TM}$ as follows On input ...
3
votes
2answers
107 views

context free grammar problem

$L$ is the context free grammar over $\{a, b\}$ $S \rightarrow aSb \; | \;bR \; |\;Ra$ $R \rightarrow bR \;|\;aR\;|\;\epsilon$ Briefly describe this CFG with English sentences and prove your ...
0
votes
2answers
46 views

context free grammar design

Design a context free grammar and PDA for the following language. $$\Sigma = \{0,1\},\qquad L = \left\{uv \mid u \in \sum^{*} \;v\in \sum^{*}1\sum^{*} \text{ with }|u| \geq |v| \right\}$$ I'm not ...
3
votes
2answers
89 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
703 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
209 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
199 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
139 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 ...
9
votes
2answers
380 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
672 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, ...