# Questions tagged [regular-languages]

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

1,552 questions
Filter by
Sorted by
Tagged with
27 views

### Proof that truncation of a regular language is regular [duplicate]

Let $L_1$ be a regular language and $L_2$ any language. I want to prove that the language of $L_1$ truncated by $L_2$ is a regular language, i.e. $$\{w| wx\in L_1 \text{ and } x\in L_2\}$$ is ...
58 views

### DFAs are regular languages, but regular languages are closed under concatenation

I have course notes which claim the following two facts: First, DFAs recognize exactly the regular languages. Second, regular languages are closed under union, concatenation, and *. Now I have as an ...
161 views

### CFG-Infinite recursion

As you see, the string production process never ends. Can someone explain me if this language is regular or not ? $S \to Α Β S$ $A \to S$ $B \to a B b$
108 views

### Myhill-Nerode to prove a language is non-regular

L = {a^n b^2n c^3n | n∈N^+} I'm trying to prove that L is a non regular language using Myhill-Nerode theorem.
176 views

### CFG that generates $1^*$ is decidable

I read somewhere that the problem which asks whether or not a CFG $G$ generates $1^*$ is decidable. The proof goes like this: $1^* \cap L(G)$ is context free since it is the intersection of a regular ...
84 views

### Pumping Lemma,regular languages

Lets say that we have the language L = { $a^n$$b^m$$c^{m+n}$ $|$ $m$,$n$ $>=0$ } What is the way that i should follow to prove that the language is not regular? Assume that the language is ...
39 views

### validation of a pumping lemma proof for regular languages

I have the following regular expression: Of course I could think of a word like $w=a^{m+2}b^{m+2}c^{2m+3}$ and continue with the proof BUT I was just wondering, because $L$ is made up of a union of ...
49 views

### Prove $\{a^ib^i\mid i\ge0\}$ is not regular using the pumping lemma

I do not understand the last sentence of the proof provided. It says that the fact that xz does not belong to L contradicts the hypothesis, but isn't it that xyz not belonging to L what we are trying ...
52 views

### What is Pumping length for Union of Regular languages?

This is an exam question. For E = {a,b}. let us consider the regular language $L= \{x|x = a^{2+3k} or x=b^{10+12k}, k >= 0\}$ Which one of the following can be a pumping length (the constant ...
1k views

### Minimum pumping length of (01)* [duplicate]

Michael Sipser offers the definition: The pumping lemma says that every regular language has a pumping length p, such that every string in the language can be pumped if it has length p or more. If p ...
146 views

2k views

### Prove or Disprove: an infinite intersection of regular languages is a context-free language

Let $L_1, L_2,...$ and $L=\cap_{k=1}^{\infty}L_k$ be languages over $\Sigma ^{*}$. Prove /Disprove: if $\forall k\in \mathbb{N}$, $L_k$ is a regular language, then $L$ is a context-free language. I ...
31 views

241 views

39 views

### Natural Languages

Can one imply that natural languages can be described by regular grammar? Is that what happens through NPL? Trying to understand the subject of how spoken language can be converted to data and how.
203 views

### Given regular languages $L$, $M$. Is $K=\{uw | u,w \in \Sigma^*,(\exists v \in M) uvw \in L\}$ necessarily regular?

Question is as follows: Given regular languages $L$, $M$. Is $K=\{uw | u,w \in \Sigma^*,(\exists v \in M) uvw \in L\}$ necessarily regular? Thank you for any input.
49 views

### How to generate a DFA that recognizes a non-regular Grammar

How would you convert the following grammar to a DFA that recognizes its language? \begin{align} &G = (\{S,A,B\},\{0,1\}, S, P)\\ &P\colon &&S\rightarrow A1B\\ &&&A \...
I want to prove that $L(G) = \{01; 11110; 10101; 000\}$ is regular. Is it correct if I write there exists a regular expression, which is: $(01|11110|10101|000)$? How can I also prove it using a DFA?
How to check if $L = \{c^ka^nb^n \mid k>0 \wedge n\geqslant0\} \cup \{a, b\}^*$ is regular ,where $L_1 = \{c^ka^nb^n \mid k > 0 \wedge n\geqslant0\}$ is clearly not regular and \$L_2 = \{a, ...