# Questions tagged [regular-languages]

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

1,609 questions
Filter by
Sorted by
Tagged with
84 views

### Closure of regularity under the action of replacing identical pairs of letters

Given any regular language L, we define $$shrink(L) = \{ \sigma_{1}\sigma_{2}\sigma_{3}...\sigma_{n} : \sigma_{1}\sigma_{1}\sigma_{2}\sigma_{2}\sigma_{3}\sigma_{3}...\sigma_{n}\sigma_{n} \in L \}$$ ...
61 views

### Proof regular languages are closed under homeomorphism

Let $\Sigma_1 , \Sigma_2$ be alphabets. Let $L\subseteq \Sigma_1^*$ be a regular language, and let $h:\Sigma_1^* \rightarrow \Sigma_2^*$ be a homomorphism. Proof $h(L)$ is regular. I have written a ...
60 views

### Is the union of infinitely many regular languages always regular? [duplicate]

Prove or disprove or this statement: The union of an infinite number of regular languages is regular. Can someone help?
44 views

### Prove by contradiction that the language with unequal number of a's and b's is not regular

Consider the language $$L = \{w \mid w \text{ has an unequal number of a’s and b’s}\}$$ where Σ = {a, b}. Prove that L is not regular. Hint: Try proof by contradiction. Would this be the right Answer: ...
79 views

### Is language decideable (subset)?

I'm working on a proof for following question $L=\{(R,S)\mid \text{R,S are regular expressions and } L(R)\subset L(S)\}$. Show that this language is/isn't decidable. A language is decidable iff we ...
21 views

### Is my proof for the regularity of the language $A/B$ correct?

This problem is from Sipser's Theory of Computation 3rd Edition. 1.35 Prove that $A/B = \{\omega \ | \ \omega x \in A \ \mathrm{for\ some \ } x\in B\}$ is regular where $A$ is regular and $B$ is any ...
256 views

### Closure of regular languages under permutation [duplicate]

Given a regular language $L$ over the alphabet $\Sigma = \{a,b,c,d\}$, is the language $\mathrm{Perm}(L)$ consisting of all permutations of words in $L$ also regular? My intuition says it is, since ...
80 views

### Understanding the definition of a language

Could you please help me understand the following Language $L = \{ a | a ∈ \{0, 1\}^∗, |a| = k ≥ 4, a = a_1a_2...a_{k−1}a_k, ∃i ∈ N, 1 ≤ i < k : a_i = a_{i+1} \}$ what does $a_i = a_{i+1}$ mean? ...
92 views

### Pumping lemma for regular languages. Proof

Please help me understand the following $L = \{ a | a ∈ \{0, 1\}^∗, |a| = k ≥ 4, a = a_1a_2...a_{k−1}a_k, ∃i ∈ N, 1 ≤ i < k : a_i = a_{i+1} \}$ To prove: The language $L$ has regular pumping ...
48 views

### $L^{\prime}=\{x \# y \mid x y \in L, y x \notin L\}$ where $L$ is regular

Hey I'm trying to prove that the following Language is regular so far couldn't find a way, hope someone can help me $L^{\prime}=\{x \# y \mid x y \in L, y x \notin L\}$ where $L$ is regular.
46 views

### Prove that not all languages over unary alphabet are regular

Let the alphabet be $\{0\}$. I have to prove that not all languages over this alphabet are regular, using some countability argument. My Ideas: The set of all languages over $\{0\}$ is uncountable. ...
122 views

### Proving that the language $\{ w^n\mid w \in \{0,1\}^∗, \, n \ge 2 \}$ is not regular

I'm trying to prove that the following language is not regular: $$\{ w^n\mid w \in \{0,1\}^∗, \, n \ge 2 \}$$ I'm trying to prove this with the pumping lemma, but I'm kind of confused because $w$ is ...
53 views

### Undecidability of an Intersection

1)"Given a CFL L and a regular language R, is the intersection of L and R an empty set?" decidable? 2)What if we replace L with the complement of L? Either 1 or 2 is decidable and the other ...
54 views

166 views

### Minimal number of states for an NFA of all different words

Given $\Sigma =\{0,1,@\}$, I am looking at a language $L=\{u@v | u,v\in \{0,1\}^k\wedge u\neq v\}$. So $u,v$ have only $0,1$s, same length $k$, yet are different. Also, for me $k$ is a known constant. ...
55 views

### Closure of regular languages under interchanging two different letters

Given any deterministic finite state automata $M$ over any alphabet, I need to construct an FSA $M'$ that accepts the set of strings $M$ accepts, but with two different letters interchanged. For ...
42 views

### Given two DFA's accepting the same language, does one have to refine the other?

I have a logical question that I can't quite crack: Given two automata accepting the same language $L$, does one have to refine the other? In other words, if $A_1$ and $A_2$ both accept $L$, with ...
77 views

### Is there a bound on possible Dead state in a minimized DFA

I want to know if a DFA is minimized, is there an upper bound on how many dead states are possible when it is in its minimal form, in terms of number of states, etc? Intuitively, I am thinking that it ...
59 views

### Language of decimal encodings of cubes is not regular

Prove that the language that consists of cube numbers as strings is not regular. I wanted to use pumping lemma but couldn't $$0, 1, 8, 27, 64, 125, 216, \dots$$
420 views

### Irregularity of $\{ w_1 aa w_2 \mid |w_1| \neq |w_2| \}$

I'm currently struggling to come up with a proof that the following language is irregular: $$L_2 := \{w_1aaw_2 \in \Sigma^* \mid w_1, w_2\in\Sigma^* \land |w_1| \ne |w_2|\}$$ where $\Sigma = \{a, b\}$....
93 views

### Converting a regular expression to a context-free grammar

Does this conversion look right? I am learning conversion from RE to CFG. RE: $$(a \cup b)^* \cup ab(a \cup b)^*$$ CFG: Terminals: $$S_1 \to a \\ S_2 \to b$$ This is for the first $(a + b)^*$: \...
25 views

103 views

### Regular language as finite union of periodic sets

Is it true that every regular language can be expressed as a finite union of periodic sets? In other words, if $L$ is regular, then do there exist finite sets $A_1,\dots,A_n,B_1,\dots,B_n$ such that ...
62 views

### Is $\{a^mb^nc^n \mid m,n \geq 0\} \cup \{b,c\}^*$ regular or not?

Show if $L = \{a^mb^nc^n \mid m,n \geq 0\} \cup \{b,c\}^*$ is regular or not. My attempt: I think the Pumping lemma won't work in that constellation, so I'm working with "The intersection of ...
869 views

### Why LL(1) grammar generate all regular languages?

I came across following: Every regular language has right linear grammar and this is LL(1). Thus, LL(1) grammar generates all regular languages. I tried to get that. Definition: Right linear ...
59 views

124 views

### Is the language of binary strings that contain a substring of the form $ww$, where $w \in (0+1)(0+1)^*$ regular? [duplicate]

Consider the language: $L=$binary strings that contain a substring of the form $ww$, where $w \in (0+1)(0+1)^*$. I am convinced this language is not regular, as $w$ can have arbitrary length due to ...
22 views

### How to describe this language a* (ba (cf* (g ( f +h )* bf* )* e )* a* )* in words?

I was task to describe this regular expression a* (ba (cf* (g ( f +h )* bf* )* e )* a)* informally. My attempt at describing it informally = any number of a followed by any number of one b one ...
5k views

### Does DPDA accept all regular languages?

A DPDA which accepts by empty stack cannot accept all Regular Languages? Is it true that the DPDA cannot accept all regular languages? I am not able to understand this.As per my knowledge DPDA are ...
66 views

### Construct a grammar for $\{a^n(bc)^m : m,n \ge 1, m < n/2\}$

I'm new to writing languages in context-free or regular grammar, so I'm struggling how to do this one. It is a bit more complicated that simpler ones I've practiced doing. The problem is to construct ...
83 views

80 views

### Regularity of language obtained by interleaving $a,b$

Let $L$ be a regular language on an alphabet $\Sigma$. and let $L^{ab} = \{\sigma_1a\sigma_2b...\sigma_n \mid \sigma_1...\sigma_n \in L\}$ be the language obtained by add between any two letters of ...
24 views

### Give the Regular-Expression (NFA) with specific Separation Patterns

Question: Given the RE (or NFA) for the set of all strings over $\Sigma ={a,b}$ such that: a occurs the odd number of times and each pair of a are separated by exactly $2n+2,n\geq 0$ b's. Attempt: ...
81 views

### Counting substrings that belong to a regular language

Given a regular language $L$ and a string $x$ give an efficient algorithm to count the occurrences of substrings $x[i,j] \in L$. More in particular, I am looking for a linear time algorithm in the ...
37 views

### Regular set of the "does not contain" kind

Given a language $L$ and a set of strings $\Sigma^* = \{0, 1\}^*$, how can I find a regular set that expresses $L = \{ w \in \Sigma^* \mid w$ ends with $00$ and does not contain $11\}$? Well, the part ...
51 views

### Show that the Language is irregular

I was solving some problem from past test, there was this question: Use the closure property of regular language to show the language $L$ is not regular $$L =\{ a^3 b^n c^{n-3} \mid n>3\}$$ I ...
189 views

### Regular languages closed under prefix operation

Suppose that $D$ is a regular language over an alphabet $A$. How can I prove that the following language is also regular? $$\mathrm{LANGUAGE}_2(D) := \{ d \mid d,t \in A^* \text{ and } dt \in D \}$$ ...
I have the language $L = \{ dkd\space \mid d \in \{a,b\}^*, k \in \{a,b\} \}$ and i have to show that it's non-regular using the pumping lemma. The structure of the language i think can be explained ...
I have the following regular expression $R=ab^*(\epsilon \cup c) \cup c^*a$ and I want to construct the NFA that accepts languages defined by that regular expression. I started by constructing the NFA ...