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.

200 questions
Filter by
Sorted by
Tagged with
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^*\}$...
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 ...
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 ...
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$ ...
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.
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 ...
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 ...
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*} \...
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$....
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 ...
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 ...
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 ...
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 ...
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 }$} ...
5k views

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 ...
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 ...
442 views

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 ...
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 |...
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 ...
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 ...
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 ...
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 ...
107 views