The tag has no wiki summary.

learn more… | top users | synonyms

25
votes
6answers
3k 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 ...
10
votes
2answers
102 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 ...
7
votes
5answers
428 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 ...
6
votes
3answers
212 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 ...
6
votes
1answer
106 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 ...
5
votes
4answers
795 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 ...
4
votes
3answers
2k 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 ...
4
votes
2answers
84 views

Prove that $\{1, 11, 1001,\dots\}$ is an irregular language

Let $L:=\{1, 11, 1001,\dots\}$ be the language with alphabet $\{0,1\}$ which is formed by all powers $3^n, n=0,1,\dots$ written in binary notation. How to prove that $L$ is not regular?
4
votes
3answers
227 views

Deciding equivalence of regular languages

Given two regular expressions $R$ and $S$ on an alphabet $\Sigma$ it is possible to decide their equivalence as follows: build two finite automata $M_R$ and $M_S$ such that $L(R) = L(M_R)$ and $L(S) ...
4
votes
1answer
58 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 ...
4
votes
1answer
71 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 ...
4
votes
1answer
944 views

Myhill Nerode - is language regular or not?

I'm trying to understand how to find equivalence classes of a language to prove its regularity. I think that if I'm able to FULLY understand one example then I will get this topic right. Let's say I ...
4
votes
1answer
670 views

Routing Automaton

Is there a formal proof for the following question? For a DFA $M= (Q,\Sigma,\delta,s,A)$, we extend the function $\delta : Q \times \Sigma^* \to Q$, such that every $w \in \Sigma^* $, ...
4
votes
2answers
117 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 ...
4
votes
2answers
168 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: ...
3
votes
2answers
1k views

How to guess whether a language is regular or not

I have a few languages and I am not given whether they are regular or not. If I had to prove their irregularity, then it would not have been difficult. How do I go about finding if the language is ...
3
votes
3answers
126 views

Showing $L=\{uw \mid \exists v:uv\in L_{1},vw\in L_{2}\}$ is regular

Let $L_{1,}L_{2}$ be regular languages and define $L:=\{uw \mid \exists v\in\Sigma^{*}:uv\in L_{1},vw\in L_{2}\}$. I wish to prove that $L$ is regular using only closure properties (such as ...
3
votes
2answers
366 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 ...
3
votes
2answers
92 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 ...
3
votes
2answers
124 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?
3
votes
4answers
5k views

Intersection of two deterministic finite automata?

I'm trying to solve a problem where I have to create a DFA for the intersection of two languages. These are: $$\{s \in \{{\tt a}, {\tt b},{\tt c}\}^\ast : \mbox{every ${\tt a}$ in $s$ is ...
3
votes
3answers
73 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 ...
3
votes
2answers
1k 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? ...
3
votes
2answers
103 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 ...
3
votes
1answer
97 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$, ...
3
votes
1answer
100 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$ ...
3
votes
1answer
4k 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 ...
3
votes
2answers
47 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 ...
3
votes
1answer
174 views

Formal Reduction: Pushdown Automata recognizing context free languages with bounded stack

I am studying for an exam in automata theory and I am having trouble solving the following: Consider pushdown automata and context free languages. Show that the following decision problem is ...
3
votes
1answer
124 views

Confusion related to the concatenation of two grammars

I have this confusion. Lets say I have two languages produced by type 3 grammar such that L(G1) = <Vn1,Vt,P1,S1> L(G2) = <Vn2,Vt,P2,S2> I need to ...
3
votes
1answer
35 views

Irregular $a^nb^n$

We studied in class that regular languages closed under intersection. My question is : if we take the irregular language $L =$ {$a^nb^n : n\geq 0$} and the regular finite language $L' = \{a^3 ...
3
votes
1answer
115 views

Does the Halting Problem apply when evaluating programs that are regular languages?

Here is my understanding of the Halting Problem: It is impossible to write a program H that can determine for any arbitrary program ...
3
votes
1answer
30 views

How do you prove that the set of neighbors of $L$ is regular if $L$ is regular?

I know that a regular language can be made into a DFA, so can I just make a DFA for the regular language? Also, someone told me I should make a e-NFA from the DFA, but I don't see what would be the ...
3
votes
0answers
68 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 ...
3
votes
1answer
288 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} ...
2
votes
3answers
143 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 ...
2
votes
3answers
122 views

Regular Language

Prove that the language $\{a^{k} \mid k \equiv 0 \text{ or }k\equiv 2 \pmod 5\}$ is a regular language. I am just trying to figure this problem out for my own benefit. I am new to learning this ...
2
votes
3answers
2k 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.
2
votes
2answers
260 views

Pumping Lemma Excercise

I am having a really tough time proving the following language is not regular using the pumping lemma. This whole time I have been working on pumping lemma problems, the variable of the power has been ...
2
votes
2answers
79 views

Is $L = \{\omega : \omega\text{ contains exactly one 'foobar'}\}$ regular?

Is the language $L = \{\omega : \omega\text{ contains exactly one 'foobar'}\}$ regular? I have a hunch that it is non-regular because a regular expression representing the language must remember that ...
2
votes
2answers
820 views

The language that contains no proper prefixes of all words of a regular language is regular

Let $L$ be a regular language. I need to prove that the language $$M_L = \{w \in L \; | \forall x \in L \; \forall y \in \Sigma^+ : w \neq xy \}$$ that contains all words of L that do not have a ...
2
votes
2answers
65 views

Proof for the amount of states of a regular language

Let L be a formal language. Two words $u,v \in \Sigma^*$ are called separable if $\exists w \in \Sigma^* : uw \in L, vw \not\in L$. Nerode lemma: Let L be a formal language. If there are $n$ ...
2
votes
3answers
96 views

Show that the language is not regular using the pumping lemma.

I have to show that the language $L = \{ a^k b^k \mid k > 0 \}$ is not regular using the pumping lemma. I have done the following: Let $i \geq 1$ $$x = a^i b^i \in L$$ $$|x| = 2i \geq i $$ ...
2
votes
2answers
939 views

suffix regular language

Can someone give me an idea how to prove this: suffix(L) = {y | xy $\in $ L for some x $\in$ $\Sigma$ *}. Or suffix is the set of all suffixes of its strings. Prove that if L is regular, then so is ...
2
votes
2answers
603 views

Prove that a language B is regular

here is the question I'm dealing with: Let B = {$1^{k}$y|y $\in$ {0,1}* and y contains at least k 1s, for k $\geq$ 1}. Show that B is a regular language. Can I use the pumping lemma to ...
2
votes
2answers
41 views

“The regular languages over $A$ are the homomorphic pre-images in $A^*$ of subsets of finite monoids.”

I'm trying to understand the statement: The regular languages over $A$ are the homomorphic pre-images in $A^∗$ of subsets of finite monoids. which appears in the Wikipedia article on free ...
2
votes
2answers
94 views

Giving a regular grammar for the language

I am trying to brush up on my regular grammar knowledge to prepare for an interview, and I just am not able to solve this problem at all. This is NOT for homework, it is merely me trying to solve ...
2
votes
1answer
80 views

Is there a problem with this example?

In example $1.14$ on page $51$ (of the book and $64$ of this link), shouldn't the string $01000$ get rejected? However it seems that the first three digits of the string would force it to an accept ...
2
votes
2answers
127 views

Is this proof using the pumping lemma correct?

I have this proof and it goes like this: We have a language $L = \{\text{w element of } \{0,1\}^* \mid w = (00)^n1^m \text{ for } n > m \}$. Then, the following proof is given: There is a $p$ ...
2
votes
2answers
113 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 ...