31
votes
Accepted
Proving Equivalence of Two Regular Expressions
One way to prove that two regular expressions $r_1,r_2$ generate the same language is to show both inclusions:
Show that if $w$ is generated by $r_1$ then it is generated by $r_2$.
Show that if $w$ ...
- 270k
19
votes
Do Turing machines have memory registers?
A TM does not have a register, but a register has a fixed capacity.
Any amount of fixed capacity storage can be emulated by multiplying your states: your new states become $ \langle q, v \rangle$ ...
- 4,696
11
votes
Accepted
Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?
$\newcommand{\m}{\operatorname{\%}}$
Let $d(w)=(|w|-\#_a(w))\m3$, where $n\m 3$ is the remainder of dividing $n$ by $3$ as defined in almost every programming language.
Note $L=\{ w\mid d(w)=0\}$.
...
- 34.9k
10
votes
Accepted
Can the diagonal language be empty?
Here is a simple direct proof that $L_{\text{diag}}$ is not empty.
Let $N$ be a Turing machine that does not accept any word. For example, a Turing machine that just loops forever. Suppose $N$ is ...
- 34.9k
8
votes
Accepted
Do Turing machines have memory registers?
Yes a TM also has states. Formally, one can define TMs as $(Q, \Sigma, \Gamma, \square, \delta, q_0, \bar{q})$ with states $Q$, input alphabet $\Sigma$ not including the blank symbol $\square$, tape ...
- 1,464
8
votes
Accepted
Is this language a context-free language or not?
No, $L_1$ is not necessarily context-free.
For example, let $L=\{0^n1^{3n}\mid n\ge0\}$.
If $ uv=0^n1^{3n}$ and $|u|=|v|$, then $u=0^n1^n$ and $v=1^{2n}$. We have $u^Rv^R=1^n0^n1^{2n}$.
So, $L_1=\{1^...
- 34.9k
7
votes
Accepted
Is $a^nb^mc^k$, $n\neq m$ and $m\neq k$ context-free?
No, $L=\{a^nb^mc^k\mid n\neq m,m\neq k\}$ is not context-free.
A proof by Ogden's lemma
Assume $L$ is context-free.
Let $p$ be the constant given by Ogden's lemma. Let $s=a^{p+p!}b^pc^{p+p!}\in L$. ...
- 34.9k
6
votes
Context free grammar for a language that is a complement of another
I would like to add that the language $L_0=\{a^n b^m c^k\;|\;n+m=k\}$ is the deterministic context-free language, and a DPDA can be constructed recognizing $L_0$ by the final state. Then we can use ...
- 565
6
votes
Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?
The following language is not regular $L = \{a^n b^m c^n \mid m = n \bmod 2\}$.
To see that $L$ is not regular, suppose towards a contradiction that $L$ is regular and let $p$ be its pumping length. ...
- 23.9k
5
votes
Accepted
A computable language with a non-computable language that is prefix-free
No, since the change from a language to its smallest prefix-free sub-language is computable.
Suppose language $L$ is computable. That is, we can list all words in $L$ in nondecreasing length. Scanning ...
- 34.9k
5
votes
Accepted
NFA: How does it function with empty-string moves?
There is only one empty string, which you denoted by $\epsilon$. If you concatenate two empty strings, then you just get the empty string back: $\epsilon\epsilon = \epsilon$. This is the same as $0+0=...
- 270k
5
votes
Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?
Lucky enough, your case is quite easy. The language is defined by the rule "total number of letters, modulo 3, equals total number of a's, modulo 3". This is equivalent to "number of ...
- 25.6k
5
votes
Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?
So far every language that I saw containing modulo was a regular language.
As John L. notes, that's a very good observation. Indeed, any language where the only constraint on words is that some ...
- 2,055
4
votes
Accepted
Can you diagonalize a language out of CSL?
This is accomplished by the nondeterministic space hierarchy theory, given that CSL is the same as $\mathsf{NSPACE}(n)$.
- 270k
4
votes
Dragon book exercise 4.4.5, why is aaaaaa not recognized by the recursive descent parser?
When you look at the parser's process, you see the entire text to be parsed, and naturally make judgements based on that knowledge. But that's not the way the parser works. So your strategy makes it ...
- 11.3k
4
votes
Accepted
Size of minimal DFA
If you consider the language over $\Sigma = \{a, b\}$ defined by the set of words that contain a $a$ in the $n$-th position before the end, or formally:
$$L_n = \{uav\mid u,v\in \Sigma^*, |v| = n-1\}$$...
- 7,203
4
votes
Proof that the complement of a finite language is always an infinite language
The set $\Sigma^*$ is an infinite set (you can build a bijection between the naturals and the words in $\Sigma^*$ if you wish to prove this, or you can observe that, for every $k \in \mathbb{N}$, $\...
- 23.9k
4
votes
Context-free grammar for $\{1^i0^j1^k \mid i+2j=k\}$
The simplest solution to problems of this form is usually to just rearrange the terms.
We know that $k = i + 2j$, which is the same as $2j + i$. So the language's sentences are of the form $1^i0^j1^{...
- 11.3k
4
votes
Accepted
How to build a deterministic finite automaton from a given one with a new definition for automaton language?
Your second construction seems to work well.
This can be formalized by starting with the formal definion of an automaton and specifying the components of the new one.
So for $\mathcal A=(Q,\Sigma,\...
- 27.7k
4
votes
NFA: How does it function with empty-string moves?
$\epsilon$ is a typographical convention, not a part of the underlying mathematical object. It's written where writing nothing would leave a confusing or ambiguous empty space.
Transitions labeled $\...
- 1,451
4
votes
Accepted
How to identify Context-Sensitive Grammar?
You are right: the grammar in your example is strictly speaking not context-sensitive. It is a monotonic (or non-contracting) grammar. In those grammars the main restriction is that the lefthand side ...
- 27.7k
4
votes
Accepted
Proof that a minimal DFA for a finite language has exactly one trap state
Recall that in the minimal DFA, each state corresponds to an equivalence class of the Myhill–Nerode relation.
All words which are not a prefix of a word in $L$ form an equivalence class $X$, which ...
- 270k
4
votes
Context free grammar for a language that is a complement of another
There's no procedure for creating a context-free grammar for the complement of a context-free language, because the complement of a context-free language might not be context-free, and the question of ...
- 11.3k
4
votes
Proving Equivalence of Two Regular Expressions
If you wanted to prove this extra formally, you could try to prove this in a proof assistant, such as Lean (or Coq or Agda or ...). Here's how you can state that problem using Lean's ...
- 143
4
votes
Accepted
Why 2- way DFA is equivalent to NFA (and thus DFA)?
The language $L=\{ (u\#,v\#) \mid |u|=|2v|\}$ from your question is actually a two-dimensional language, that is a relation between two strings, each written on their own input tape. In that way the ...
- 27.7k
4
votes
Accepted
Are the set of all Bitcoin addresses a context-sensitive language?
Any answer I give you is likely to be unsatisfying and a little silly, both because we're squarely in theory-land here (and not the useful kind of theory, but theory that is irrelevant in practice), ...
D.W.♦
- 143k
4
votes
Accepted
Formal grammar of MIU system
As Hendrik Jan remarked, the MIU-rules as a string rewriting system is not a semi-Thue system. Each string rewriting rule in a semi-Thue system does not care about context. A step of rewriting in a ...
- 34.9k
3
votes
Is language $a^mb^nc^n, m \not= n$ context free
The reason that $L_1$ is context-free is that one needs to keep track of only two numbers at the same time: either $l=m$ or $m=n$. The 'or' is handled using union, we patch two languages together.
The ...
- 27.7k
3
votes
Accepted
PDA with multiple element access - $i$ - access PDA
Hint: replace every $d$-depth transition with a set of states and transitions that will read out $d-1$ elements, then read the last element and do the transition, and afterwards return the last $d-1$ ...
- 10.9k
3
votes
Accepted
How to write a non-ambiguous grammar for the syntax of lambda calculus?
You certainly don't need a context-sensitive grammar to solve this problem (and it probably wouldn't help you, either). In fact, you can solve it with the precedence declarations available in most ...
- 11.3k
Only top scored, non community-wiki answers of a minimum length are eligible