# 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 ...
148 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 ...
558 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 ...
371 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 ...
122 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

### Application of Pumping lemma for regular languages

I need to proof by using the Pumping lemma that the language $L = \{0^m1^n \;|\; m \geq n\}$ is not regular. According to the Pumping lemma for each regular language a word $w = xyz$ exists, that ...
243 views

### Pumping Lemma proofs

I am having a hard time writing a Pumping Lemma contradictory proof for the below statements. 1) $L_1 = \{ ww \mid w \in E^* \}$ <--- I don't understand how to read this. This is what I tried: ...
110 views

### This proof in my textbook involving the pumping lemma appears incorrect - is it?

It states Let $B$ be the language $\{0^n1^n2^n | n \geq 0\}$. We use the pumping lemma to prove that $B$ is not regular. The proof is by contradiction. Assume to the contrary that $B$ is regular. ...
11k views

130 views

### Creating a regular grammar

Hi I am trying to write a grammar for $L=\{xcy \mid x \neq y^R \land x,y \in \{a,b\}^*\}$. I am not able to think beyond a point as to how to write the grammar. Could someone guide me?
101 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 ...
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$, ...
36 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. ...
123 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 ...
32 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 ...
22 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 ...
64 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 ...
37 views

### Regular languages- homomorphism.

Let $h: \{ a,b,c,d \}^* \rightarrow \{a,b\}^*$ be a homomorphism such, that $h(a) = aa, h(b) = ab, h(c) = ba, h(d) = b$ . Determine: $h^{-1}((bab)^*ba^*b).$ I have trying do it by 4 hours. I don't ...
39 views

### Why is $\left\{a\right\}^*\cap L(A)=\emptyset$? where $\delta(q,a)=q$

I am trying to solve this particular problem from Automata Theory by Ullman, Hopcroft, it is as shown below : Let $A$ be a $DFA$ and $a$ be a particular input symbol of $A$, such that for all states ...
56 views

### Equivalence of two regular expression

I have a quick question to ask. So I am trying to come up with a regular epxression which represent a language over {a,b} that contains at least one 'b' in it. I came up with this: (a| b)^*b(a| ...
67 views

### Injective map, that maps context-free languages to regular languages

Let $\Sigma \neq \emptyset$ be an alphabet. Is there an injective map $f: \Sigma^* \rightarrow \Sigma^*$ such that for every context-free language $L \subseteq \Sigma^*$ the set $f(L)$ is a regular ...