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.

learn more… | top users | synonyms

5
votes
4answers
1k 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 ...
0
votes
2answers
41 views

Regular expression 00 or 11 not both

Can anyone help me with this question: I know it before, but I have tried to solve it myself and didnt succeed. what is the regular expression for this language: L=all words that have 00 or 11 but not ...
5
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
4answers
7k 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
3answers
3k 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.
1
vote
2answers
98 views

Formal Languages - Regular Expression

I've been battling the following two questions for more than a day today. Write a regular expression (comprised of {a, b}) that contain at least two b and do not contain abb. Write a regular ...
2
votes
2answers
462 views

If $L$ is regular, prove that $\sqrt{L}=\left\{ w : ww\in L\right\}$ is regular

Let $L$ be a regular language. Prove that $\sqrt{L}:=\left\{ w : ww\in L\right\}$ is also a regular language. I suppose I need to modify state machine for $L$ to accept $\sqrt{L}$, but I've been ...
26
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 ...
4
votes
3answers
288 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) ...
1
vote
1answer
32 views

Write the regular expression of the language that the DFA accepts.

I am given a DFA and I have tried to write the regular expression of the language that it accepts. This is the DFA that I am given: I have found some words that the DFA accepts: ...
1
vote
1answer
157 views

Possible solution for Sipser 1.63

Sipser's question 1.63: Let A be an infinite regular language. Prove that A can be split into two infinite disjoint regular subsets. Is my solution correct? Since $A$ is infinite and ...
1
vote
1answer
191 views

Prove the following language is not regular

The set of strings of 0's and 1's, beginning with a 1, such that when interpreted as an integer, that integer is prime. I'm assuming the best way to move forward is to use the pumping lemma. I'm ...
1
vote
1answer
372 views

A regular expression for the words that don't contain the sequence $ab$ over $\{a,b,c\}$

The following is an exercise in a book I am reading: Let $\Sigma=\{a,b,c\}$, define $L$ to be the language of all words over $\Sigma$ that do not contain $ab$ as a sub-word. Find a regular ...
0
votes
0answers
90 views

Prove that whenever L is a regular language so is HasPrefix(L)

For a language $L$ over an alphabet $\Sigma$, define the language $\operatorname{HasPrefix}(L)$ as follows: $$\operatorname{HasPrefix}(L) = \{xy\mid x,y \in\Sigma^*, x \in L, xy \in L, |y|> 0\}$$ ...
2
votes
1answer
32 views

Non regular language that satisfies pumping lemma

Let $$L = \{ ww^rx \mid w,x \in \{a,b \}^+\} $$ where $\{a,b\}^+$ means the set of words over $\{a,b \}$ that has at least length 1, and $w^r$ is the reverse of $w$. I'm trying to prove that this ...
2
votes
1answer
41 views

Prove that this language is not regular

I need to prove that the language $$L = \{a^nb^mc^k|n+k\neq3m\}$$ is not regular. Any ideas how I can do that?
2
votes
2answers
143 views

Can an infinite set of primes be a regular language or CFG?

At first glance, it seems like the pumping lemmas should somehow "easily" show that an infinite set of primes (say, written in binary) cannot be a regular language or context-free grammar. But I don't ...
2
votes
1answer
126 views

Are languages regular if their concatenation is regular?

Let $A, B \subset \Sigma^*$ be languages. If the concatenation product $AB$ is regular, are $A$ and $B$ necessarily regular? I'm inclined to think this is true since the regular language $AB$ has a ...
2
votes
2answers
316 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
49 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 ...
1
vote
2answers
57 views

Prove that the language $\{bin(p) \mid p\ \text{is prime}\}$ is not regular (prime numbers)

Prove that the language $\{bin(p) \mid p\ \text{is prime}\}$ is not regular, where $bin(p)$ denotes the binary representation of $p$. I should use the pumping lemma. But I have a problem. Could you ...
1
vote
2answers
30 views

FSM to be regular with atleast two 0's and at most two 1's

Is it possible to construct a FSM to prove that the set $X$ is regular, where $$ X = \{s \in \{0,1\}^* \mid \text{$s$ contains at least two $0$'s and at most two $1$'s}\}\ ? $$
1
vote
1answer
41 views

Give a regular expression for $A = \{1^{k}y|k \geq 1, y \in \{0,1\}^{*}$ and $y$ contains at least $k$ $1$'s $\}$

The regular expression that is given is $1(0 \cup 1)^{*}10^{*}$. I'm having trouble realizing why this regular expression describes the language given. For example, the string (for $k$ = 4) $1111$ ...
1
vote
1answer
61 views

Working with the word w⋅y, while given the word y⋅w

$L$ is a regular language. I am given $F(L)$ such that $$F(L)= \{wy \mid yw\in L\}$$ I need to prove that if $L$ belongs to $L_\text{dfa}$, $F(L)$ also belongs to $L_\text{dfa}$. I am having a hard ...
1
vote
1answer
68 views

proving by construction that language is regular

I had this exercise saying the following: $$ L =\{w\mid w = w_1xw_2 \land w_1, w_2, x\text{ are words }\land w_1w_2 \in L_1 \land x \in L_2\} $$ I need to prove that $L$ is regular by defining an ...
1
vote
1answer
1k views

Showing that a language is not regular using Myhill-Nerode Theorem

I'd like to show that the language below is not regular using Myhill-Nerode Theorem. How can I do that? Thanks in advance. Let $Σ = \{0, 1, +, =\}$ and $\mathrm{ADD} = \{x = y + z \mid x, y, ...
1
vote
2answers
241 views

Prove that [ContextFreeLanguage - RegularLanguage] is always a context free language, but the opposite is false

Let L be a context-free grammar and R a regular language. Show that L-R is always context-free, but R-L is not. Hint: try to connect both automata) The above hint did not help me :(
0
votes
0answers
41 views

Is the following language $L$ regular?

$L=\{ww^Rv\mid v,w\in \{a,b\}^+\}$ Is $L$ regular ? Edit Is it ok? Let $p$ will be length of pumping lemma. Then, $a^pb(a^pb)^Rv\in L$. When $a^p(a^pb)^Rv = xyz$ $p\ge |y|\ge 1 $ So ...
0
votes
4answers
60 views

prove that language is not regular (prime numbers)

$$\sum_{p\,\in\,\text{Prime}}(cb^*)^p + (b+c)^*cc(b+c)^*$$ Show that language is not regular. We see that there are two possibilities: $p$ (prime) blocks of $b's$ separated by $c$ or any string of ...
0
votes
2answers
63 views

Determine whether $L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\}$ is regular.

Given the alphabet $\Sigma=\{a, b\}$ and for the next Language $L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\}$ determine whether the language is regular. Firstly, I think this language is regular. ...
0
votes
2answers
128 views

Pumping Lemma to show a language is not regular

Let $\Sigma = \{a, b\}$. Use the Pumping Lemma to show that $\mathcal L = \{ a^pab^q: p < q \}$ is not regular. Not sure how to apply PL here, if someone can give some direction.
0
votes
1answer
160 views

Is this language regular?

Given $m,n∈Z$, A is a finite alphabet set ,and $L=\{(a^m,a^n)\}^*$ is subset of $A^*\times A^*$ . Is this language regular ? For example, is $L=\{(a^3,a^7)\}^*$ regular ? Here L is not the set ...
0
votes
1answer
85 views

Algorithm for checking if regular language has given property

Give an algorithm that will decide (in any finite time) if given regular language $L$ (given by some regular expression) has given property: $$\forall_{x\in L} \exists_{y\in L} \left( \left(x\neq ...
0
votes
3answers
2k views

Is there a subset of a non regular language that is regular

I am just curious is there any non regular language whose subset is regular?