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