The regular-language tag has no wiki summary.
23
votes
5answers
2k 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 ...
6
votes
3answers
128 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
84 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
3answers
349 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
2answers
60 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
132 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
53 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
54 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
2answers
103 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
95 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
46 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
205 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
97 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
2answers
660 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 ...
3
votes
2answers
89 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
79 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
59 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
165 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
2answers
447 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 ...
2
votes
3answers
108 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
80 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
2answers
75 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
162 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
215 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
53 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
2answers
57 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
72 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
78 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
79 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 ...
2
votes
1answer
25 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 ...
2
votes
4answers
2k 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 ...
2
votes
1answer
17 views
If $\{w^k|w\in L\}$ regular implies L regular?
If L is a language and the language
$$\tilde{L}:=\{x^k,x\in L, k\in\mathbb{N}\}$$
is regular, does that imply that L is regular? ($|L|<\infty$ gives equivalence)
We came across this question when ...
2
votes
1answer
77 views
Pumping Lemma problem
Apply pumping lemma to each of these and prove that they are not regular.
$L = \{ (0^p)(1^q)2 \mid 0 < q < p\}$
$L_2 = \{ (a^p)(b^q)(c^r) \mid p = q \text{ or } q = r\}$
Here my ...
2
votes
1answer
132 views
Proving a language is regular or irregular
I am having a really difficult time writing proofs for these problems. I would greatly appreciate any suggestions for a strategy on how to look at such problems and begin writing a proof. Trying to ...
2
votes
1answer
34 views
Why is $S(L)$ regular?
Let $L$ be a regular language, and $\Sigma$ be its alphabet. Then, the language $S(L) = \{y \in \Sigma^*~|~xy \in L \text{ for some string }x \in \Sigma^*\}$ is also regular.
I am trying to ...
2
votes
1answer
168 views
How to draw this finite state automaton?
I know that the following language $L$ = {$a^n$ where $n$ is a prime number bounded by some fixed $f$} is a regular language because it is finite. Because it's a regular language, I should be able to ...
2
votes
1answer
24 views
Regular composition of non-regular language
I've got the following problem:
Let's take language $L$.
Is it posible that $L$ is not regular itself,
but it's composition $L\cdot L$ becomes regular?
I suspect that's correct, yet I ...
2
votes
1answer
65 views
Is $L = \{a^{n+2} b^n | n \ge 0\}$ context free or regular?
Is the language $L = \{ a^{n+2} b^n | n \ge 0 \}$ context free? If so, what is a context free grammar for it? If it is regular, what is a right linear grammar for it?
2
votes
1answer
437 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 ...
2
votes
1answer
27 views
Regularity of “middles” of words from regular language
I need some help with the following problem: $L$ - regular language and i have to prove that the language $P$ = {$\alpha$| $\beta\alpha\gamma \in L$, $\beta,\gamma \in (A)^*$} is regular. In other ...
2
votes
1answer
213 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 ...
2
votes
1answer
47 views
Is regularity is preserved under reversal?
When talking about languages and regular languages.
Can I say that reversal preserved regularity since if the language L is regular, we can generate it by right linear grammar.
Therefore, the ...
2
votes
2answers
67 views
For the language $\{w \mid w \in \Sigma^*, w \neq \lambda\}$, is the following regular expression correct?
For the language $\{w \mid w \in \Sigma^*, w \neq \lambda\}$, is the following regular expression correct?
$(a+b)^+$ . Which is $(a+b)$ to the power of $+$ which I think accepts all combinations of ...
2
votes
1answer
106 views
Is the set of codes of Deterministic Finite-State Automata a regular language?
Let $\Sigma$ be a given alphabet. Is there a way to code up Deterministic Finite state Automata (DFA) over $\Sigma$ as strings of $\Sigma$ in such a way that the corresponding subset of $\Sigma^*$ is ...
2
votes
1answer
61 views
Proving that languages are not regular
The Nerode Lemma can be used to show whether a language is regular or not. This can be done in several ways but I need to do it by providing a set of separable items.
Example:
The language of ...
2
votes
1answer
171 views
Constructing finite state automata corresponding to regular expressions. Are my solutions correct?
I have drawn my answers in paint, are they correct?
(4c) For the alphabet {0, 1} construct finite state automata corresponding to each of the following regular expressions:
(i) 0
My Answer 4ci
(ii) ...
2
votes
0answers
30 views
Pumping lemma for $a^nb^{2n+1}$
I know how to solve pumping lemma for $a^nb^n:n\geq 0$.
But I don't understand how can I solve this example : $a^nb^{2n+1}:n\geq 0$.
I tried to solve it but I am not sure that I have solved it ...
2
votes
0answers
164 views
Regular, Context-free, Recursive, Recursively Enumerable Language Relationships
I am currently under the believe that all regular languages are context free, thus all regular languages are recursive, and therefore all regular languages are recursively enumerable.
If I am given ...
2
votes
1answer
118 views
Using the pumping lemma to show that a language is not regular (Computer Science)
Show that $L=\{a^{n^2} | n \ge 0\}$ is not regular
Hey guys. I'm taking a CS class and this stuff is really new to me so bear with me.
I tried to look if I get some contradiction by using the ...
1
vote
2answers
79 views
How can I prove the majority of three languages is also regular if the three languages are regular?
This is a question I've been stuck on recently:
Let $A$, $B$, and $C$ be three languages over the same alphabet. Define $\mathrm{maj}(A,B,C)$ to be the collection of all strings $w$ that occur in at ...
