# Tagged Questions

Regular languages are formal languages which are recognized by a finite automaton. It is equivalently the languages which are expressible as a regular expression. In addition to these two, there are several other equivalent definitions.

4k views

### Is the set of all valid C++ programs countably infinite?

I have heard that the set of valid programs in a certain programming language is countably infinite. For instance, the set of all valid C++ programs is countably infinite. I don't understand why ...
151 views

### Mystery Men Movie - Propositional Logic

In the movie Mystery Men, there is this scene: Captain Amazing (good guy): I knew you couldn't change. Casanova Frankenstein (bad guy): I knew you'd know that. Captain Amazing: Oh, I know. And ...
567 views

### A computer's memory is finite, so how can there be languages more powerful than regular?

A computer has a finite memory. There are no computers with infinite memory. Therefore the only languages that a computer can process are those whose member strings are finite. As I recall, the ...
13k views

### Converting to Chomsky Normal Form

I am trying to learn how to convert any context free grammar to Chomsky Normal Form. In the example below, I tried to apply Chomsky Normal Form logic, to result in a grammar, where every symbol either ...
2k views

### Why isn't this a regular language?

I'm stuck as to figuring out why $L_1$={$n^p$ | $p$ = a prime number} is not a regular language but $L_2$={$n^p$ | $p$ = a prime number bounded by some fixed number f} is. I can see that $L_2$ is a ...
384 views

### Reductions for regular languages?

To reason about whether a language is R, RE, or co-RE, we can use many-one reductions to show how the difficulty (R, RE, or co-RE-ness) of one language influences the difficulty of another. To reason ...
124 views

### Existence of NFA for this language

I'm given a task to find (and prove) such language $L$ in the alphabet $\Sigma = \{a,b\}$ with all words less than $1000$ in length, for which any DFA/NFA will have more than $10^{10}$ of states. For ...
4k views

45 views

### Can a regular grammar be ambiguous?

An ambiguous grammar is a context-free grammar for which there exists a string that has more than one leftmost derivation, while an unambiguous grammar is a context-free grammar for which every valid ...
8k views

### Formally prove that every finite language is regular

I know how to prove this informally, but don't know what the formal proof should look like.
446 views

### Number of states in a finite automaton

How many states are required by a deterministic finite automaton to store $m$ words each of length $n$? I came across $2^{mn}$ as the solution but there was no explanation.
3k views

### Are regular languages necessarily deterministic context-free languages?

The original problem Suppose M is DCFL (Deterministic Context Free Language) and N is a regular language. Answer the following questions and justify your answers. a) Is M-N necessarily context-free? ...
159 views

66 views

### $\{\langle M,q,x\rangle$| $M$ is a Turing machine and $q$ is a state of M and running of $M$ on $w$ visits $q\} \notin R$?

I'm trying to find where does the language $\{\langle M,q,x\rangle$| $M$ is a Turingmachine and $q$ is a state of M and running of $M$ on $w$ passes on $q\}$ belong? whether it's $R,RE$ or none of ...
85 views

### Proving that a language build from two regular languages is regular as well

Let $L, M \subseteq \Sigma^*$ be regular languages. I need to prove that $$N = \{x \in \Sigma^* \; | \; \exists y \in L : xy \in M\}$$ is as well a regular language. My favored approach is to find a ...
42 views

127 views

### Number of states required to recognize $\{ ss : s \in \{ 0 , 1 \}^*, |s| = i \}$ and its complement

$$\Sigma = \{0,1\}\;\\ S_{i} = \left\{ss: s\in {\Sigma}^{*} \text{and s has length i}\right\}$$ Prove that for any $i$, any DFA recognizing $S_{i}$ must have $2^{i}$ or more states. Design a ...
56 views

### Finding a general formula for a regular expression

I need to find the general formula for the regular expression $(S+T)^n$ where $S$ and $T$ are arbitrary regular expressions over a one-letter alphabet and $n$ is an arbitrary natural The general ...
59 views

### proving that $L_\text{almost}$ is a regular language

Let it be L, a regular language. we will define: $L_\text{almost} = \{ w'\mid \exists w\in L\ w' \text{ is almost similar to }w \}$ a word $w'$ is almost similar to $w$ if they are in the same length,...
123 views

### Applying the Myhill-Nerode Theorem

Consider the language $$L=\{x y^{(n)} z y^{(n)} w: x,z,w \in \Sigma^*, y \in \Sigma, z\text{ does not contain }y, n \geq 0 \}.$$ To show that the language is not regular using the Myhill-Nerode ...
492 views

### Notation of cross entropy

I have a question regarding a notation that seems to be very usual. For starters, cross entropy is defined by: \begin{align}H(X, q) &= H(X) + D(p||q) \\ & =-\sum_x p(x)\log_2 q(x)\end{align} ...
343 views

### Pumping lemma contrapositive

I have a few questions about Pumping Lemma Contrapositive. First of all, how do I choose pumping length $n$? Is it just any constant from the language definition? i.e. I have $L=\{a^kb^gc^hd^j\}$ so I ...