34
The fundamental theorems of formal language theory are that regular expressions, regular grammars, deterministic finite automata (DFAs) and nondeterministic finite automata (NFAs) all describe the same kinds of languages: namely the regular languages. The fact that we can describe these languages in so many completely different ways suggests that there's ...
21
I'm a bit confused by your question: you're asking if the Turing machine is recognizable, but I think you mean to ask if the language $\{1^x \mid x \in \mathbb{N}\}$ is recognizable.
A language is recognizable if and only if we can build a Turing machine that accepts every string in the language, and does not accept any string not in the language. And we ...
13
So my question is:
(Why) Is my proof wrong?
If it is right: Why is there no easy way to express permutations?
Your "proof" only looked at permutations of single words, which are finite languages.
Every finite language is regular (e.g. just by listing all of the members with a | inbetween), but there are infinite regular languages (and those ...
11
Being regular is a property of languages, not of words.
However, it seems that by '010' you really mean the language consisting only of the single word '010', that is, $\{ 010 \}$. This language, just like any other finite language, is regular.
Where does your pumping lemma proof fail, then? Here is a complete statement of the pumping lemma.
If $L$ is a ...
9
The proof of Brzozowski's result is technical, but not very complicated.
In fact we only have to consider one sequence of reversal-determinization, to obtain the minimality result we want. (The first sequence of reversal determination leads to a deterministic FSA for the reversal of the original language; the minimality proof is for the second reversal-...
8
It's a "trick" question. The language is regular because
\begin{align*}
\{aba^{\mathrm{R}}\mid a,b\in\{0,1\}^*\}
&= \big\{\varepsilon b\varepsilon^{\mathrm{R}}\mid b\in\{0,1\}^*\big\}
\cup \big\{a b a^{\mathrm{R}}\mid a\in\{0,1\}^+,\ b\in\{0,1\}^*\big\}\\
&= \{0,1\}^*
\cup \big\{a b a^{\mathrm{R}}\mid a\in\{0,1\}^+,\ b\in\{0,1\}^...
8
A popular reference is the article Undecidable Problems for Context-free Grammars by Hendrik Jan Hoogeboom.
The following is a proof taken from this note by Rob van Glabbeek.
Theorem: It is undecidable whether or not the languages generated by two given context-free grammars have an empty intersection.
Proof: By a reduction of post correspondence problem (...
7
Yes.
Lautemann and Schwentick prove that Greibach's "hardest context-free grammar" with a neutral symbol is complete for $LOGCFL$ and hence $CFL$ also, under quantifier-free projection without BIT.
This is Corollary 4.3 in their paper
7
Let $\Sigma$ be an alphabet of size $n$. A regular expression describing all permutations of $\Sigma$ must have exponential size. This follows from Theorem 9 in Lower bounds for context-free grammars, which gives an exponential lower bound on the much stronger model of context-free grammars (a regular expression of size $m$ can be converted to a context-free ...
7
According to Parikh's theorem, if $L$ were context-free then the set $M = \{(a,b) : a \leq \gamma b \}$ would be semilinear, that is, it would be the union of finitely many sets of the form $S = u_0 + \mathbb{N} u_1 + \cdots + \mathbb{N} u_\ell$, for some $u_i = (a_i,b_i)$.
Obviously $u_0 \in M$, and moreover $u_i \in M$ for each $i > 0$, since otherwise ...
6
We can take it even further: if we put a limit on the size of the HTML/XML, say 1PB, then there is only a finite number of them, so we can trivially parse them in $O(1)$ using a giant look-up table. However, that doesn't seem to tell us much about the complexity of parsing HTML/XML in practice.
The issue at stake here is modeling. A good model abstracts ...
6
Write the word $s'$ as
$$
s' = 0^{(p-\beta)} \left(1^p01^p0^{\beta} \right)0^{(p -\beta)}
$$
to see that it is in fact in $L$.
6
Your use of the pumping lemma is incorrect. First, to show that the pumping lemma fails to hold in the case of your string $S$ (and thereby prove $L$ non-regular), you would have to show that every choice of $y$ fails. You've picked a specific $y$.
Second, $S'$ is in $L$. Simply take the whole $S'$ string as $b$ and let $a$ be empty. Every string of zeros ...
6
Slightly more formally, for an alphabet $\Sigma$, the language of repetitive strings over $\Sigma$ is defined as follows.
$$ RR = \{w: w=uyyv \text{ for some }u, y, v \in \Sigma^*, y \text{ is not empty}\}$$ The question is, is RR a regular language?
There are three cases.
$\Sigma$ has one symbol.
WLOG, let $\Sigma=\{a\}$. Then $RR = aaa^*$ is a regular ...
6
The language $L_2$ is not necessarily regular. Indeed, consider $A = a^*b$. If $L_2$ were regular, then so would the following language be:
$$L_2 \cap a^*ba^*b = \{ a^nba^nb : n \geq 0 \}.$$
However, this language is not regular (exercise).
In contrast, the language $L_1$ is regular. We can see this by constructing a DFA for it. Let the DFA for $L_1$ have ...
6
This is not possible. A DFA on a one symbol alphabet is a directed graph with out-degree 1. The walk one follows from the start state consists of a (possibly zero length) path followed by a cycle. As all sufficiently long strings are accepted, all states in the cycle must accept. If the DFA has at most 11 states, a walk of length 23 must be in the cycle, so ...
6
Languages are sets of finite strings. Every input to a Turing machine is a finite string. $1^\infty$ is a thing, but not in this model of computation (and usually we're more specific about what infinity we're talking about).
6
I assume you can already prove that the union, intersection, and complement of regular languages is regular.
Let $L_1$ be regular and $L_2$ be non-regular. Then you should also be able to prove:
At most one of $L_1 \cup L_2$ and $L_1 \cap L_2$ is regular.
If $L_1 \subset L_2$ then their union is irregular. (You should also be able to construct an example).
...
6
Every variable except $\gamma$ in this answer stands for a positive integer. It is well-known that given an irrational $\gamma>0$, there is a sequence of rational numbers $\dfrac{a_1}{b_1}\lt\dfrac{a_2}{b_2}\lt\dfrac{a_3}{b_3}\lt\cdots \lt\gamma$ such that $\dfrac{a_i}{b_i}$ is nearer to $\gamma$ than any other rational number smaller than $\gamma$ whose ...
6
No, just take as counter example $L_1=\epsilon$ and $L_2$ any other langage different from $L_1$.
6
Every $LL(k)$ grammar is $LR(k)$, but there are $LL(k)$ grammars which are not $LALR(k)$.
There's a simple example in Parsing Theory by Sippu&Soisalon-Soininen
$$\begin{align}S &\to a A a \mid b A b \mid a B b \mid b B a\\
A &\to c \\
B &\to c
\end{align}$$
The language of this grammar is finite, so it is obviously $LL(k)$. (In this case, $...
5
"From what I understand, there is not an algorithm to determine whether my guess is correct." It looks like your understanding is wrong.
There is no algorithm that determines whether any given formal language grammar is ambiguous context-free. There is no algorithm that determines whether any given formal language grammar is inherently ambiguous context-...
5
(Answer adapted from an almost identical question on StackOverflow, because it really belongs here.)
It's certainly possible to write a grammar for this language, but it won't be a context-free grammar. That's easy to demonstrate using the pumping lemma.
The pumping lemma states that for any context-free language, there is some integer $p$ such that any ...
5
The language of palindromes over $\{0,1\}$ is context-free, but every Myhill–Nerode class is a singleton. So your claim is wrong for context-free languages (unless the alphabet is unary). In contrast, regular languages have a finite number of Myhill–Nerode classes, so at least one of them has to be infinite. The same is true for context-free languages over a ...
5
"How do I make sure that $b$'s can be put anywhere in between $a$'s in v and u?"
Hint, you may need another non-terminal.
Here is a hint about the higher-level approach to the question although you did not ask for it, since it looks like you are not in the reasonably correct way to move forward. I would also encourage you to go forward with your approach as ...
5
Multiple passes do not add any power.
It's possible to do all the passes in parallel, using a state machine whose states are vectors of states in the original machine. Each vector has one element for each state in the original machine, and represents the result of performing the transitions starting at the state corresponding to the position of the element ...
5
A language $\mathcal L$ is recursive if there exists a Turing machine $\mathcal M$ (and therefore, an algorithm) that stops on every input, and that accepts exactly words from $\mathcal L$ (i.e. $\forall w, \mathcal M$ accepts $w\iff w\in\mathcal L$). Designing a Turing Machine that doesn't comply with those conditions won't help you prove that there isn't ...
5
The number of words of given length in a language is a very natural parameter. Here are some examples to pique your interest:
The density of $(1+01)^*$ is the Fibonacci sequence.
The density of a regular unary language is eventually periodic.
The density of a regular language is of the form $\Theta(n^k \lambda^n)$ for some integer $k \geq 0$ and real $\...
4
Evidence against the effective decidability of the problem is provided by the construction in the proof of Theorem 9 in my paper On Practical Regular Expressions: You could determine if there are finitely many Fermat primes.
4
The class of regular languages is closured under various closure operations, such as union, intersection, complement, homomorphism, regular substitution, inverse homomorphism, and more. This can be used to prove that a given language is not regular by reduction to a language which is already known to be non-regular.
As a very simple example, suppose that we ...
Only top voted, non community-wiki answers of a minimum length are eligible
