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$ ...
user avatar
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$ ...
user avatar
  • 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\}$. ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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^...
user avatar
  • 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$. ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
  • 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=...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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)$.
user avatar
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 ...
user avatar
  • 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\}$$...
user avatar
  • 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}$, $\...
user avatar
  • 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^{...
user avatar
  • 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,\...
user avatar
  • 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 $\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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), ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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$ ...
user avatar
  • 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 ...
user avatar
  • 11.3k

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