# 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 ...
153 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 ...
575 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 ...
387 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 ...
127 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

49 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.
481 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 ...
89 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 ...
44 views

128 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 ...
58 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 ...
170 views

613 views

### Question about regular languages and finite automata

We say a language $L$ is regular if it is accepted by some finite automaton $M$. I would like someone to clarify this definition. Given a finite automaton $(Q, \Sigma, \delta, q_0, F)$, we define the ...
99 views

### If $L\in REG$ then $M$ has a finite number of distinct rows

Let $L \subseteq \Sigma^{\star}$ and let $M^{\Sigma^{\star} \times \Sigma^{\star}}(\{0,1\})$ an infinite matrix such that for each $x,y\in \Sigma^\star$:  m_{x,y}=\begin{cases} 1 & x y\in L\\ 0 &...
102 views

### Is $L = \{(x,y,z) | x+y=z\}$ a regular language?

Suppose $x,y,z$ are coded as decimal or their binary representations in an appropriate DFA. Is $L$ regular? My intuition tells me that the answer is no, because there are infinitely many combinations ...
143 views

### Is $\frac12 L$ a regular language?

Let $L$ be a regular language. Is $\frac{1}{2}L := \left\{ w: \exists_u |u|=|w| \wedge wu\in L \right\}$ regular too? I think the answer is YES. But I don't know how to prove it. I was trying to ...
179 views

Let $L$ be a regular language over the alphabet $A=\{0\}$. Is it true that the language of binary representations of $n$, such that $0^n\in L$ is regular?
111 views

### Does A* = A when A contains an even number of 0s?

In class, my professor proposed the following: Let $A = \{w \mid w \text{ contains an even number of$0$'s} \}$ where $\Sigma=\{0,1\}$ is the alphabet. And then asked the class whether $A^* = A$, ...
39 views

### Is C* regular if C is a language with strings of prime length?

Let $C = \{a^p \ | \ p \ \text{is prime}\}$ be a language. I was able to show that $C$ is not regular using the pumping lemma. However, I am having some trouble showing that $C^*$ is regular. ...
124 views

### reverse automata mininum states

There is a formal proof for the following sentence? For every $k$ there is a DFA (deterministic finite automaton) $M$ with $k+2$ states such that every automaton that accepts the language $L(M)^R$ ...
148 views

### Basic regular expressions problem

I'm in an intro to CS theory class learning about regular expressions. I was wondering if people could give me hints as to whether I'm on the right track for these problems. I hope this particular ...
41 views

### Finding the mistake in a new way of generating FSMs from regular expressions

As described e.g. here (see pp. 2-3) a final state machine can be easily constructed from a regular expression. For the union of to expressions $e + f$ I need to look at the original way of ...
37 views

### subsets of non regular language

I know that there are many languages that are context free but not regular like $\{a^n b^n :n>0\}.$ But I want to know if every context free but non-regular language has infinitely many non-regular ...
23 views

### Language of binary multiplications relation.

Given $\Sigma = \lbrace 0, 1 \rbrace$ and $L \subseteq (\Sigma \times \Sigma \times \Sigma)^*$. Let $first(w), second(w), third(w)$ be word from $(\Sigma \times \Sigma \times \Sigma)^*$ limited to ...
131 views

### Pumping lemma and $L \subset \{a\}^*$

Let $L \subset \{a\}^*$ and $L$ satisfies pump lemma. Prove that $L$ is regular. Please help me. My an attempt: Definition. A language $L$ of $A^∗$ is recognized by a monoid $M$ if there is a ...
66 views

### A Regular Expression for all strings that…

I got a problem I have to solve, the problem says that given an alphabet $\Sigma = \{a, b, c\}$ I have to build a regular expression that describes the string with: An even number of a's. A 4k + 1 ...