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

1
vote
3answers
68 views

Prove that this language is not regular (Pumping Lemma)

Prove that the following language is not regular. I have no clue where to start. $$L = \{ a^n b^n c^n \mid n \geq 0 \}.$$
1
vote
1answer
48 views

Is $L=\{w\mid \text{ same number of 010 and 101}\}$ regular?

I tried to prove that this language is regular using NFA or regular expressions and didn't succeed. I would like to see some solutions
0
votes
1answer
93 views

Prove or disprove that the language $L_1 = \{a^nb^m \mid n < m \}$ is regular

I have possible strategy for a proof that it is not regular. I am wondering if it is valid. Step 1: Prove that the language $L_2 = \{a^nb^n\}$ is not regular (for example with the Pumping Lemma). ...
0
votes
1answer
47 views

Prove L is not a regular language (A Finite State Automaton cannot accept it)

$$\mathscr L = \{x \in \{0,1\}^* \mid \text{there is a } y \in \{0,1\}^* \text{ such that } x = yy\}$$ How can I prove that this is not a Regular language? I tried using proof by contradiction but ...
1
vote
2answers
215 views

How to solve pumping lemma questions?

I am trying to prove that L = { aNbMaN-M|N>=M>=0} is not regular using the pumping lemma. I am pretty confused how to solve this. What I have so far (which I am not sure is right) is: Assume L is ...
1
vote
1answer
55 views

Checking some Regular Expression problems

I'm given the alphabet $$ \Sigma = {\{a,b}\} $$ I tried to write a regular expressions for presenting the following sets: All strings in $$\Sigma ^ *$$ with: a-) number of 2s divisible by 4 b-) ...
1
vote
1answer
26 views

How to prove the following related with regular languages

How can we prove the following. If $$\sum$$ is any alphabet and L is any language $$L \subset \sum*$$ Then L*L* = L* ?
2
votes
2answers
74 views

Prove the following by using mathematical induction

If we define the alphabet such that $$ \Sigma = {\{a,b}\} $$ and let $w$ be a string over it. I'd like to prove $$ ( \operatorname{comp}(w))^R = \operatorname{comp}(w^R) $$ where $$ w^R$$ and ...
0
votes
1answer
35 views

Question about Notation in a Regular Language

I am a little confused about the following notation: $L' = \{xy|x\in L \ , y\in L^R\}$. I think this expression is not equivalent with palindrome but I am not entirely sure. For example, I think the ...
1
vote
2answers
67 views

Prove by induction on a string

I want to practice proving the following: Given a binary string s, I want to prove $s$ has the same number of substrings 01 and 10 $\iff$ the first and last character of $s$ is the same. For ...
2
votes
1answer
44 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| ...
0
votes
1answer
29 views

How can I show ithat a language is regular?

I have a very quick question about regular languages, I think $\{a^{2n}| n\geq 1\}$ is regular. I do know that pumping lemma can be used to show something that is not regular. I am wondering what ...
0
votes
1answer
42 views

Question About Pumping Lemma used on a FA

I am learning about pumping lemma and I am trying to solve a problem. I need to use pumping lemma to show that: the Language L(M) defined by the following machine is infinite. Here is the dfa: ...
4
votes
0answers
89 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. ...
0
votes
2answers
117 views

Regex for strings with at least three unique characters

I'm trying to represent some string conditions in terms of regex. One of those conditions I find hard to transform is that the string must have at least three different characters. So is there any ...
3
votes
3answers
84 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 ...
0
votes
3answers
2k views

Regex for strings with no three identical consecutive characters

I wanna ask what the regular expression for the strings having the property in the title should be. For binary string with no three consecutive 0, it's quite a simple regex ...
2
votes
1answer
743 views

Complement of a regular expression?

What is the regex for the complement of $r = b^*(ab + a^* + abb(b^+))^*$ ? I am thinking $(a+b)^*(abb)^+a^* $ since anything that contains $abb$ and is not followed by $b$'s would not be accepted ...
3
votes
1answer
35 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 ...
2
votes
1answer
1k views

Proof of Equivalence of NFA and DFA, quick question about the setup

I am looking at the proof of equivalence of non determinstic finite automata(NFA) and deterministc finite automata(DFA). I am have a small quesion about the construction: Let ...
2
votes
1answer
132 views

Pumping Lemma for regular languages proof template

http://www.cs.uiuc.edu/class/fa06/cs273/Lectures/pumping-lemma/pumping-lemma.html So, I went to that site and it says: $w = xyz$ $|xy| \leq p$ $|y| \geq 1$ for all $i$, $xy^iz$ is in ...
0
votes
1answer
249 views

Show that two disjoint languages are not separable

What is the general method to show that two disjoint languages are not separable? As an example, suppose we have: $A = \{\langle M \rangle : M ( \langle M \rangle )$ halts and says ACCEPT$\}$ $B = ...
0
votes
1answer
93 views

showing language that is non-regular using pumping lemma

I am looking over pumping lemma and the author is using it to show that the language is non-regular. {a^n b^n a^n} = {aba aabbaa aaabbbaaa........} Is there ...
0
votes
1answer
51 views

Struggling with Proof Writing. Simple question for demostration.

I am practicing writing proofs over regular expressions. Here is the question: Show that $(r\cup \varepsilon)^*= r^*$, where $r$ is a string. Intuitively, the left hand side is the concatenation of ...
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$ ...
0
votes
2answers
163 views

Prove the language $\{a^k b^l : k \neq l \}$ is not regular

Prove that the following language is not regular: $$L=\{a^k b^l : k,l \ge0, k\ne l\}$$ The problem is that I should use "distinguished states" not the pumping lemma, which is usually used for such ...
1
vote
1answer
50 views

Regular languages and intersection

Let L be a language and R an infinite regular one. If L intersection R is a regular language, then L is a regular one too?
1
vote
1answer
58 views

Question about equlaity of two language, simple but tricky.

I found the following question tricky: If $A$ is a language, when will $A^*=A^+$? By definition, $$A^* = \bigcup^{\infty}_{i=0}A^i = A^0 \cup A^1 \cup A^2 \cup \cdots$$ $$A^+ = ...
1
vote
2answers
24 views

A question about operations on languages.

I come across this problem on a book. It states that: for languages A and B, $(A\cup B)^* = (A^*B^*)^*$. I know that the definition of star closure is $\left(\bigcup^{\infty}_{i=1}\right)A^i$. But so ...
2
votes
1answer
56 views

A correct proof for this pumping lemma example?

Given the language $L = \{0^{2^n} | n \geq 1\}$ So, the language contains all strings that have $2^n$ $0$s. First of all I take $z = a^{2^p}$ where $p$ is the constant guaranteed by the pumping ...
0
votes
1answer
53 views

Regular language restricted to smaller alphabet is regular

Let $L$ be a regular language on some alphabet $\Sigma$, and let $\Sigma_1 \subset \Sigma$ be a smaller alphabet. Consider $L_1$ the subset of $L$ whose elements are made up only of symbols from ...
0
votes
1answer
26 views

Is the language regular or contextfree?

Could you tell me if the language $$L=\{ w \in \{a,b,c\}^*: $$$$\text{there is at least one time the substring abc and none of the symbols a,b,c is repeated three times} \}$$ is regular or ...
0
votes
1answer
31 views

Use closure properties for the language $L=\{a^kb^l:|k-l| \leq 100 \}$

Given the language $$L=\{a^kb^l:|k-l| \leq 100 \}$$ I have to show that $L$ is regular or context free using closure properties. I have done the following: The language is regular. Let $k>l$, then ...
0
votes
1answer
30 views

How can I show that the language is regular using the closure properties?

How can I show that the language $L=\{ w \in \{a,b\}^*: \text{ the word w contains an even number of a and an odd number of b} \}$ is regular using the closure properties?
1
vote
1answer
50 views

Pumping Lemma Squares Proof Explanation

I'm looking for some help understand this perfect squares proof using the pumping lemma. Here is the proof: I don't understand how n^2 + k < n^2 + n towards the end of the proof. Would anyone ...
0
votes
2answers
401 views

Regular expression and DFA/NFA questions

If a language L is generated by a regular expression, then L is recognized by a DFA. I think this is true, because regular expressions describe regular languages, those of which are exactly ...
1
vote
1answer
37 views

Is the language L regular?

Could you tell me if the language $L=\{a^ib^j:i+j=k, k \geq 2 \}$ is regular? Do I have to find a regular expression for this language? Or what can I do to check if $L$ is regular or not?
2
votes
1answer
166 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 ...
0
votes
1answer
41 views

Is it necessary that X is also regular?

Given that $L$ is a regular language and $X \subseteq L$,does $X$ have to be also regular?
1
vote
1answer
25 views

DFA for {any sequence of a and b, between two consecutive “b” there are maximum 3 “a”}

I have tried to draw a deterministic finite automaton for the language L={any sequence of a and b, between two consecutive "b" there are maximum 3 "a"}: Is it correct?
1
vote
3answers
176 views

NFA for $(ab|a)^{*}$ using only 2 states

In Introduction to the Theory of Computation by Michael Sipser, there's an example which shows how to convert the regular expression $ (ab|a)^{*}$ into an NFA. The "standard" method results in 8 ...
1
vote
1answer
71 views

is this language regular or not?

I have problem with this language $$L = \{ a^n b^m : \text{$n+m$ is odd} \}$$ is it regular or not My Solution I used pumping lemma, w = a^2p b^2p+1 (the same for a^2p+1 b^2m ) ...
0
votes
1answer
86 views

Finding regular expressions

I'm given the DFA shown below and need to find regular expressions for the following languages: $L_{1,2}^0, L_{2,1}^6, L_{2,5}^4, L_{2,3}^5, L_{1,3}^5$. The language $L_{p,q}^r$ is defined as ...
1
vote
1answer
263 views

Finding Nerode equivalence classes

How am I supposed to find the equivalence classes of a Language? What should I think? For instance, having a language $$L =\{a^n b^m \mid n,m \ge 0, (m+n) \bmod2=0)\}$$ I can have: $[a^n]$ with ...
1
vote
3answers
60 views

regular language question

Good afternoon everyone; I am stuck with a question I could not find and answer by myself I hope you can help me. My question is The language L = {w : w {a,b}*, |w| is odd, w has exactly one b}. ...
0
votes
1answer
39 views

Is this a regular language? Number of a's greater than $k$

Prove/disprove: $L = \{ w \mid |w|_a \geq 2k \}$, where $\Sigma = \{ a,b\}$ and $k$ is a constant, is a regular language. Intuitively I am saying yes, it is a regular language. But I don't ...
0
votes
1answer
53 views

Show that the language is regular modifying the DFA

Let L be a regular language. How can I show that the language $\text{Suffix}(L)=\{w \in \Sigma^* \mid \text{ there is a $x \in \Sigma^*$ so that }xw \in L\}$ is also regular? How can I modify the DFA ...
1
vote
1answer
253 views

Check if a regex is ambiguous

I wonder if there is a way to check the ambiguity of a regular expression automatically. A regex is considered ambiguous if there is an string which can be matched by more that one ways from the ...
1
vote
0answers
37 views

Why every regular language is in $\text{TIME}(n)$?

How can I prove that every regular language $R$ has linear time complexity, i.e. every regular language satisfies $$R \in \text{TIME}(n)$$
1
vote
1answer
259 views

DFA for Boolean Formula

Let $ f\left( b_{1}, \dots , b_{n} \right)$ be a boolean function. Define $S_{f} = \{\left( b_{1}, \dots , b_{n} \right): f\left( b_{1}, \dots , b_{n} \right)=1; b_{i} \in \{0,1\}, 1\leq i \leq n \}$ ...