The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [regular-languages]

Questions about properties of the class of regular languages and individual languages.

Filter by
Sorted by
Tagged with
2
votes
3answers
340 views

Regularity of “middles” of words from regular language

I need some help with the following problem. Let $L \subseteq \Sigma^*$ be a regular language. I have to prove that the language $P = \{\alpha \mid \beta\alpha\gamma \in L, \beta,\gamma \in \Sigma^*\}$...
2
votes
1answer
269 views

When using the Pumping lemma, how do I deal with different cases of y?

I want to prove L is not regular:$$L={\{www|w \in \Sigma^*\}}$$ $$\Sigma=\{a,b\}$$ I am sure I can do so using pumping lemma. I used $$ab^pab^pab^p$$as my chosen string but I am stuck. I do not know ...
2
votes
1answer
209 views

Can the definition of regular languages be simplified?

Wikipedia says The collection of regular languages over an alphabet Σ is defined recursively as follows: The empty language Ø is a regular language. For each a ∈ Σ (a belongs to Σ), the ...
0
votes
2answers
2k views

Are supersets of non-regular languages also non-regular?

I have to proof that if $L_1 \subset L_2$ and $L_1$ is not regular then $L_2$ it not regular. This is my proof. Is it valid? Since $L_1$ is not regular, there does not exists a finite automata $M_1$ ...
-3
votes
2answers
3k views

Are all irregular languages infinite? [duplicate]

How can I prove whether irregular languages are infinite? I thought about proving it by the definition of regular language but got stuck.
31
votes
2answers
2k views

Why is a regular language called 'regular'?

I have just completed the first chapter of the Introduction to the Theory of Computation by Michael Sipser which explains the basics of finite automata. He defines a regular language as anything ...
14
votes
3answers
28k views

Infinite Language vs. finite language

I'm unclear about the use of the phrases "infinite" language or "finite" language in computer theory. I think the root of the trouble is that a language like $L=\{ab\}^*$ is infinite in the sense ...
3
votes
2answers
3k views

Are regular languages closed under inverse homomorphism?

Let $\Sigma$ and $\Delta$ be alphabets. Consider a function $\varphi: \Sigma \rightarrow \Delta^*$. Extend $\varphi$ to a function from $\Sigma^* \rightarrow \Delta^*$ such that: \begin{eqnarray*} \...
18
votes
4answers
7k views

Using Pumping Lemma to prove language $L = \{(01)^m 2^m \mid m \ge0\}$ is not regular

I'm trying to use pumping lemma to prove that $L = \{(01)^m 2^m \mid m \ge0\}$ is not regular. This is what I have so far: Assume $L$ is regular and let $p$ be the pumping length, so $w = (01)^p 2^p$....
16
votes
3answers
768 views

Number of words in the regular language $(00)^*$

According to Wikipedia, for any regular language $L$ there exist constants $\lambda_1,\ldots,\lambda_k$ and polynomials $p_1(x),\ldots,p_k(x)$ such that for every $n$ the number $s_L(n)$ of words of ...
12
votes
3answers
2k views

Is there an efficient test for if an NFA accepts a subset of another NFA?

So, I know that testing if a regular language $R$ is a subset of regular language $S$ is decidable, since we can convert them both to DFAs, compute $R \cap \bar{S}$, and then test if this language is ...
11
votes
4answers
2k views

Star free language vs. regular language

I was wondering, since $a^*$ is itself a star-free language, is there a regular language that is not a star-free language? Could you give an example? (from wikipdia) Lawson defines star-free ...
3
votes
2answers
2k views

Proving regular languages are closed under a form of interleaving

I've got the following definitions: $$\mathrm{Interleave}\,(x,y) = \{w_1\dots w_n\mid w_i\in\{x_i,y_i\} \text{ for }i=1, \dots, |x|\}$$ when $x$, $y$ and $w$ are words with $|x|=|y|$ and $w_i$ means ...
5
votes
2answers
19k views

Proving L = {$ { a^{2^n} \ | \ n \ge 0 } $} is not regular by use of Pumping Lemma

I've been struggling with this problem for quite a while now and every explanation I have managed to find doesn't seem to correctly solve it. We have the language L = {$ { a^{2^n} \ | \ n \ge 0 } $} ...
4
votes
3answers
5k views

Irregularity of $\{a^ib^jc^k \mid \text{if } i=1 \text{ then } j=k \}$

I read on the site on how to use the pumping lemma but still I don't what is wrong with way I'm using it for proving that the following language is not a regular language: $L = \{a^ib^jc^k \mid \text{...
1
vote
3answers
7k views

Proof that the regular languages are closed under string homomorphism

Where can I find a proof of this? Thanks!
11
votes
1answer
3k views

Prove that the complement of $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties

I want to prove that the complement of $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties. I understand pumping lemma can be used to prove that $\{0^n1^n \mid n \geq{} 0\}$ is not a ...
10
votes
1answer
1k views

Is there a way to test if two NFAs accept the same language?

Or at least generate a set of strings that one NFA accepts, so I can feed it into the other NFA. If I do a search through every path of the NFA, will that work? Although that will take a long time.
8
votes
2answers
908 views

Partition an infinite regular language into 2 disjoint infinite regular languages

Given any infinite regular language $L$, how can I prove that $L$ can be partitioned into 2 disjoint infinite regular languages $L_1, L_2$? That is: $L_1 \cup L_2 = L$, $L_1 \cap L_2 = \varnothing$, ...
6
votes
3answers
117 views

First half of context-free palindromes

If $L\subseteq\Sigma^*$ is a regular language, then $\text{mir}(L) = \{ww^R \mid w\in L\}$ is context-free. This is a nice exercise. Question: does the reverse hold? Thus, if $\text{mir}(L)$ is ...
2
votes
1answer
253 views

Is vwwx regular language?

I think I understand pumping lemma for regular and context free languages, but there is this one, which I have no idea if it is regular or context free or not context free. $L = \{vwwx : v,w,x \in \{...
2
votes
2answers
193 views

Measures and probability in formal language theory

I am looking for references for the following problem: I have a very special class of regular languages and my aim is to express (and to justify my conjecture) that this class itself is very small in ...
2
votes
1answer
165 views

Regularity of language of words containing a square

$$L = \{w\mid w\text{ contains a substring of form }yy\text{, where }y\text{ is any non-empty string}\}.$$ Is this language regular? We do not know what $y$ looks like in advance. And why is this ...
1
vote
1answer
442 views

How do you convert a regular expression to its disjunctive normal form?

A regular expression $r$ is said to be in disjunctive normal form if it can be written in the form $r = r_1 +r_2 +\dots+r_n$ for some $n ≥ 1$, where none of the regular expressions $r_1, r_2, \dots, ...
6
votes
4answers
375 views

Why does $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ generate a context free language for regular $L$?

How can I prove that the language that the operator $A$ defines for regular language $L$ is a context free language. $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$, where $x^R$ is the ...
5
votes
2answers
198 views

Why is this language involving reversal regular?

For a language to be regular it needs to be recognized by DFA/NFA. Let $L = \{ xy^rzyx^r \mid |x| , |y|, |z| \ge 1 \}$ over the alphabet $\{0,1\}$. $x^r$ means the reverse of $x$. A DFA has no ...
4
votes
3answers
184 views

Language of the graph of an affine function

Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let : be a symbol distinct from any digit. Let $a$ and $b$ ...
4
votes
2answers
734 views

$L(M) = L$ where $M$ is a $TM$ that moves only to the right side so $L$ is regular

Suppose that $L(M) = L$ where $M$ is a $TM$ that moves only to the right side. I need to Show that $L$ is regular. I'd relly like some help, I tried to think of any way to prove it but I didn't ...
3
votes
1answer
237 views

Is there a DFA with $k+2$ states which its reverse has $2^k$ states

I am trying to figure out if there exists a DFA $M$ with $k+2$ states (for every $k\in \mathbb{N}$ ) so that every automaton which accepts $L(M)^R$ has at least $2^k$ states. I am trying to find an ...
3
votes
1answer
3k views

Show that the Kleene star of any unary language is regular [duplicate]

An exercise asks me to show that the Kleene star of any unary language $L$ is regular. $E$ is the alphabet, $E = \{ 1 \}$ Here's my reasoning : $L$ is regular $\implies$ $L^*$ is regular (closure ...
3
votes
1answer
557 views

Find a regular language that becomes non-regular if you cut away the middle third of all words

Let $A$ be a regular language, let $A'=\{xz\}$ such that for some $y,|x|=|y|=|z|$ and $xyz\in A$. Show that $A'$ is not necessarily regular language. This is an excercise of Sipser, I've no idea how ...
3
votes
3answers
149 views

Prove regular languages are closed under f(n) = 2^n and f(n) = n^2

Suppose $ R $ is a regular language, let $ f(R) = \{ w \mid \exists x \text{ such that } |x| = f(|w|) \land wx \in R\}$, prove that $ f(R) $ is regular for $ f(n) = 2^n $ and for $ f(n) = n^2$. I've ...
3
votes
1answer
72 views

Are there any specific mechanical ways to reduce a regular expression 'equation' to a more simple one?

So if we have a complex equation in regular algebra we can use properties like distrbuivity, associativity and commutativity to make an equation simper or more compact. Can we use some sort of ...
3
votes
2answers
1k views

Infinite Intersection/Union of regular languages

Hello I'm having trouble understanding how an intersection/union of regular languages can be regular and in other case non-regular. Can someone please give me some good examples?
2
votes
2answers
3k views

Pumping Lemma for regular language for $a^n$ where $n$ is even fails

$$L=\{a^n \mid \text{\(n\) is even}\}$$ This is regular but fails in the pumping Lemma. Assuming $m=4$, $w=aaaaaa$, $|w|=6$ (even). Let $w=xyz$, $x=a$, $y=aaa$. We have $|y|>0$ and $|xy| \le m$. ...
2
votes
3answers
100 views

proving L1* ∪ L2* ⊆ (L1∪L2)*

x∈ L1* ∪ L2* ⇔ x∈ L1* ∨ x ∈L2* ⇔ x ∈(L1)* ∨ x∈(L2)* ⇔ x ∈L1* ∪ L2* ⇔ x∈(L1∪L2)* Is it enough to prove it this way?
2
votes
1answer
215 views

Proving the Language is not regular for $(a^n)^n$

I am trying to solve a pumping Lemma Problem where $L= \{(a^n)^n ; n\ge 0\}$ I am having a lot of trouble with the pumping lemma and understanding using it with different languages. Here is what I ...
2
votes
2answers
153 views

Looking for an “intuitive” regular expression for $\{ w \in \Sigma^{\ast} \mid 2|w|_1 + |w|_0 \equiv 0 \pmod{3} \}$

Let $L \subseteq \Sigma^{\ast}$ with $\Sigma = \{0,1\}$ be the language such that two times the number of $1$'s in a word in $L$ plus the number of $0$'s is divisible by $3$, i.e. if we denote by $|w|...
2
votes
1answer
1k views

How come {ww} isn't regular when {uv | |u|=|v|} is?

As we know, using the pumping lemma, we can easily prove the language $L = \{ w w \mid w \in \{a,b\}^* \}$ is not a regular language. However, the language $L_1 = \{ w_1 w_2 \mid |w_1| = |w_2| \}$ is ...
1
vote
1answer
814 views

Write a regex to match string that does NOT contain a certain pattern [duplicate]

Let's say our alphabet is 0 and 1. How would you approach writing a regex to generate a language of words that do NOT contain 101. The only regex operators allowed are concatenation , star * and OR |...
1
vote
2answers
3k views

Proving that language $ L = \{ a^{2n}: n \geq 1\}$ is regular

I was asked to prove that language described by $$ L =\{ a^{2n}: n\ge1\}$$ is regular using pumping lemma. Pumping Lemma states that for regular language we can break down language described by ...
1
vote
1answer
314 views

Language whose intersection with a CFL is always a CFL

Prove or disprove: If the language $L$ is such that for every context-free language $L_0$, the language $L \cap L_0$ is context-free, then $L$ is regular. I haven't managed to prove this, but I'm ...
1
vote
1answer
5k views

Why is the complement of a language that is not regular also not regular?

In my lecture notes I we were given two languages and were shown that each of the two languages were not regular. The second was the complement of the first language. To show the second was not ...
1
vote
1answer
299 views

Finding regular expression for a language with more substring of one type than from another

Take the alphabet A={0,1} I need to build a regular expression for the language with less or equal substrings 011 than 110. I tried to figure out what would be the finite automata but I'm not to ...
1
vote
3answers
107 views

How can both |y| = 0 and y⁰ = ε hold in the Pumping lemma?

There is something in the pumping lemma that I do not quite understand, namely if $s$ is at least of length $p$, then we could split it to $xyz$ such that the following conditions are met: For each $...
1
vote
1answer
154 views

How do I show that $a^n w b^n$ is not regular?

Given $ \Sigma= \{a,b\} $, show that $ L:= \{a^nwb^n: m,n \in \mathbb N, m\geqslant n, w\in\Sigma^m\} $ is not regular. I'm trying to proof this with the Pumping Lemma, but I'm kind of confused ...
0
votes
3answers
3k views

Build a regular grammar for a regular language [duplicate]

The language considered is the infinite set of all chains that meet the following conditions. Conditions: ...
0
votes
2answers
48 views

Determining if $L$ = {$ { a^nsb^n : s \in L(a^*b^*) ,\ n \ge 1 } $} is not a regular language using Pumping Lemma?

In short, is this similar to how $a^nb^n$ is not a regular langauge? $L$ = {$ { a^nsb^n : s \in L(a^*b^*) ,\ n \ge 1 } $} For instance, if we have the string $w=a^psb^p$, and we know that $|xy| \le ...
0
votes
1answer
815 views

Proving following regular expressions equal to one another?

How would I go about proving the following two regular expressions are equal to one another: ( a + b )* a ( a + b )* b( a + b )* = (a + b)* ab(a + b)* I can "see"...
0
votes
1answer
507 views

Does this regular expression equal this automata?

I just came across an exercise which is to find a regular expression for the following automata, such that the regular expression and the automata generate the same language. One solution presents ...