4
Yes, it was studied before. In one of the early papers on accepting infinitary languages Landweber introduced five acceptance types that included those of Büchi and Muller. On the lowest level where two types that referred to the set of states entered, and the other three levels considered the more classic set of states entered infinitely often.
Your type is ...
3
You can write this language as the intersection of two languages:
$$
\{ x \# y \mid xy \in L \} \cap \{ y \# x \mid xy \notin L \}
$$
I assume you know how to handle the first one. As for the second one, construct an NFA that acts as follows:
Start with a DFA for $L$.
Guess which state the DFA will be on after reading $x$.
Based on this guess, verify that ...
2
Hint. Whether or not a word $u$ belongs to your language only depends on the parity of two parameters: $x(u) = |u|_0 + |u|_1$ and $y(u) = |u|_1 + |u|_2$. Computing modulo $2$, this gives you four states, $(0, 0), (0,1), (1,0), (1,1)$. It remains to find the transitions. For this, you just have to compute $x(uc)$ and $y(uc)$ for each letter $c \in \{0, 1, 2\}$...
2
Assume towards contradiction that the language is regular.
Let a be the "pumping length" given by the pumping lemma.
Let $p \geq a+2$ be a prime number. Consider the word: $w=0^p1^p \in L$.
By the pumping lemma, it can be written as $w=xyz$ where $|y| \geq 1$,
$|xy| \leq a $, $xy^nz \in L \ \ ,\forall n \geq 0$.
Consider $w' = xy^0z$.
Note that the ...
2
Given a normal form grammer $G$ for an infinite prefix-closed $L$, examine the (almost) regular grammer $G'$ obtained by transforming rules of the form $A\rightarrow BC$ into $A\rightarrow B$. I leave it to you to show that $L(G')$ satisfies your requirements.
1
This seems impossible if the translator has to be deterministic.
Let's clean up the problem and ask the PDA to convert $a^{n+m} b^n$ to $x^m y^n$ (your translator can be converted to such a translator by using a regular transducer). Since your PDA is deterministic, it cannot output anything until it knows whether $m = 0$ or not, which can happen in one of ...
1
It is possible. Practically, $a^b=a*a*a*\dots*a$, hence can be computed using a combination of the multiplication turing machine (to compute the multiplications), and the subtraction TM, in order to count the number of multiplications.
There is a reduction from multiple tapes TM to a single tape TM, so anything possible with multiple tapes is also possible ...
1
The language $L' = \Sigma^* y\Sigma^*$ is regular and, by the closure properties of regular languages, so is $\Sigma^* \setminus L'$. Then, by the closure properties of context-free languages, $L_2 = L_1 \cap (\Sigma^* \setminus L')$ is context-free (since it can be written as the intersection of a context free language with a regular language).
1
An oracle call is stronger than emulating a TM: it allows you in constant time to solve the task of checking if some $x$ is in the language specified by the oracle.
What you saw didn't use oracle machines, since it proved by assuming towards contradiction: It assumed there is a machine $M$, and showed how to use its code in order to build a new machine $M'$ ...
1
Construct the intersection DFA of both DFA's. Then, check if there is a path from the starting state to any end state.
If there is a path, then the two DFA's are not disjoint. If there isn't, then they are.
Only top voted, non community-wiki answers of a minimum length are eligible
