# Tag Info

5

The following extended regular expression matches the language $\{ ww : w \in \Sigma^* \}$: $$\texttt{^$.*$\\1\\\}$$ This language is neither regular nor context-free. Matching using extended regular expressions is NP-complete; see for example this paper, which discusses efficient algorithms in some special cases.

4

Since $0 \in A$ and $1 \in A$, any word $w \in \Sigma^*$ can be written has a concatenation of $n=|w|$ words $w_1, \dots, w_n$ such that each $w_i \in A$ (showing that $w \in A^*$). In order to do so it suffices to pick $w_i$ as the $i$-th character of $w$, i.e., $w_i$ is either $0$ or $1$.

3

This is a simple application of the pumping lemma. Suppose that $L'$ is an infinite subset of $L$. Given $p$, since $L'$ is infinite, there exists some $n \geq p$ such that $w = a^nb^n \in L'$. Let $w = xyz$ be a decomposition of $w$ such that $|xy| \leq p$ and $y \neq \epsilon$. Then $y = a^t$ for some $t \neq 0$, and so $xy^0z = a^{n-t}b^n \notin L'$. ...

3

A language $L \subseteq \{0,1\}^*$ is well-defined if, for each possible word $w \in \{0,1\}^*$, it is clearly specified whether $w$ is in $L$ or not. This means that your rules must cover every case (for every word $w \in \{0,1\}^*$, at least one of your rules specifies whether $w$ is in $L$ or not), and that there are no contradictions (there does not ...

3

Answer 1: The question is meaningless as written. You are mixing different kinds of notations here that are intended for different purposes. BNF and ABNF are concrete notations for writing the abstract concept of a context-free grammar. "Van Wijngaarden grammar" refers either to an abstract type of grammar a la "context-free grammar", or ...

2

Assuming you refer to Myhill-Nerode equivalence classes: First notice, that for a non-regular language $L$, the number of classes is necessarily infinite. This is one direction of the Myhill-Nerode theorem. Since regular languages are closed under reversal, it follows that for a non-regular language $L$, both $L$ and $L^R$ have the same number'' (namely, ...

1

The same way you would convert the definition of deterministic finite automata to a nondeterministic one: The transition function would output a set of transitions instead of a single one. This means that if in the deterministic case we have $\delta(p,a,t)=(q,u)$, now it will look like: $\delta(p,a,t)=\{(q_1,u_1),...,(q_n,u_n)\}$ for any $q_i,u_i$ we choose. ...

1

Prove that if your language contains $a^nb^n$ and $a^mb^m$ for n <> m then after parsing $a^n$ and parsing $a^m$ you end up in different states. (Proof is trivial). If there are infinitely many different n, m then the number of states cannot be finite.

1

That would be not difficult at all. We use something similar to a Turing machine with a small modification: As it runs it counts the number of steps performed. For the first $10^{1000000}$ steps it behaves like a normal Turing machine. But if it hasn’t halted by then, it keeps running forever. Obviously decidable, except that running the machine for that ...

1

Suppose that $A$ is a recognizable set containing descriptions of always halting Turing machines. We want to show that there exists a decidable language $L$ such that for any $M$ deciding $L$ we have $\langle M\rangle\notin A$. We can construct such $L$ via simple diagonalization. Assume $A$ is infinite (otherwise the problem is trivial). We will define a ...

1

Yes, what you have observed is correct. We can, in fact, always take $N=0$. Here is the variant of Jeffrey Jaffe's pumping lemma where strings are pumped up or down exactly once. A language $L$ is regular iff $\exists k$, $\forall x\in \Sigma^k$, $\exists u,v,w\in \Sigma^*$ such that $x=uvw$, $|v|\ge 1$ and $\forall z\in \Sigma^*$, uvwz\in L \iff uwz\...

Only top voted, non community-wiki answers of a minimum length are eligible