# Tag Info

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

### 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
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
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
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
Accepted

• 270k

### 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

### 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
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

### 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
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

• 11.3k
Accepted

• 1,451
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
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

### 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

### 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
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
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), ...
• 143k
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

### 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
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