# Questions tagged [regular-language]

Regular languages are formal languages which are recognized by a finite automaton. It is equivalently the languages which are expressible as a regular expression. In addition to these two, there are several other equivalent definitions.

1,261 questions
Filter by
Sorted by
Tagged with
1 vote
48 views

### Are Compactness for FOL and the Pumping Lemma for RL/CFL two instances of the same phenomenon?

As title states, I'm curious whether my intuition for the Compactness result for FOL and the Pumping Lemma for RL/CFL being two expressions expressions of the same phenomenon (that is: an attempt to ...
• 566
37 views

### Identifying whether certain palindromic languages are non-regular [duplicate]

In a nationwide entrance exam conducted in India, the following problem was asked in the year 2007: Which of the following languages are regular? (A) $L_1 = \left\{ ww^R \mid w \in \{0, 1\}^+ \right\}$...
131 views

### Getting from DFAs to regular expressions by solving a system

This question is asking if the solution $x=v^\ast w$ to the equation $$x=vx+w$$ (where all constants and variables are regular expressions) is unique or not, and the accepted answer states that it is ...
• 205
1 vote
23 views

### Is it decidable to check whether a regular language contains a word NOT of the form $uuv$? [closed]

Is the following problem decidable? Given a regular language $L \subseteq \Sigma^\ast$, check if $L \cap \{uuv \mid u \in \Sigma^+, v \in \Sigma^\ast\} \ne L$; i.e. whether there is a word in $L$ ...
• 11
23 views

### Differentiating regular expressions with squaring

Regular expressions describe languages with letters, and the operators +, . and *. Given two languages L1 and L2 described by regular expressions, we can give an exponential upper bound on the size of ...
64 views

### Show that $L$ is not regular

Let $F$ and $L$ be arbitrary infinite binary languages $\forall x,y\in F$ with $x\neq y$, there are 2 binary strings $w,z$ (possibly equal) such that $wxz\in L$ and $wyz\notin L$. Show that $L$ is not ...
• 522
1 vote
37 views

### Prove that $\{a^nb^m \mid n \leq m\}$ is not regular, using only closure properties

We can use the pumping lemma or the Myhill-Nerode theorem to prove that $\{a^nb^m \mid n \leq m\}$ is not a regular language. It turns out that the proof is kind of similar to the proof for the more ...
• 333
42 views

### Understunding how to find a regular expresion for a regular language

Let $L:=\{ \omega \in \{0, 1\}^* : |\omega|_0 \in 3\Bbb{Z}\}$ where $|\omega|_0$ denote the number of $0$'s appearing in $\omega$ . Find a regular expression for $L$ . I am studying Automaton Theory ...
26 views

### Converting generalized nondeterministic finite automata (GNFA) into regular expressions

When converting from a GNFA to a regular expression, we systematically remove states from the GNFA until we are left with just the start and accept state such that the transition arrow from the former ...
37 views

• 121
1 vote
126 views

### What is the regular language for L = {w | w has even length, and starts and ends with the same symbol}?

I think it is it 0(01)*(01)*0 U 1(01)*(01)1 where: two versions: one that starts and ends with 0, the other that starts and ends with 1 connected by plus, which ...
• 147
1 vote
112 views

### Show that, if $L$ is a regular language, then so is $\{w : \exists n \in \Bbb{N}, w^n \in L\}$

Suppose $L$ is a regular language over an alphabet $\Sigma$. Let $$L' = \{w : \exists n \in \Bbb{N}, w^n \in L\}.$$ Prove that $L'$ is regular too.
• 52.1k
1 vote
65 views

We have two languages $L_1, L_2 \subseteq \{{a, b}\}^{*}$. According to the following formulas find $L_1$ and $L_2$: $L_1 = \{\lambda\} \cup \{a\}.L_1 \cup \{b\}.L_2$ $L_2 = \{\lambda\} \cup \{b\}.... • 63 1 vote 2 answers 125 views ### Proof of irregularity of a language, L = {0^n : n is prime} So the above statement is a question from a course on Theory of Computation. I have already proven it using the pumping lemma, but am looking for proofs using the Myhill-Nerode theorem, or more ... 2 votes 1 answer 111 views ### If$L$is regular, is$L' = \{xz \mid \exists y, y \in \Sigma^* \text{ such that } |x|=|y|=|z|\text{ and }xyz \in L\}$regular? I know how that if the condition$|x|=|y|=|z|$is relaxed, then we get another regular set, as is shown by the construction in this question or this one. But I am not able to solve for this case when ... 1 vote 1 answer 74 views ### Why do we need empty string transitions in the NFA intended to accept this singleton language? Consider the attached NFA (from Sisper's Introduction to the Theory of Computation, 3e) which has been deduced in order to accept precisely the language containing the string$ab$. The rest of the ... • 1,163 0 votes 1 answer 81 views ### Is the Language$L=\{(ab)^{3n}\:|\:n\in\mathbb N\}$regular? Is the language regular? My application of the pumping lemma suggests: splitting it in$xyz$: $$x = \emptyset \mid y= (ab)^{j} \mid z=(ab)^{3n-j}$$ Pumping up$y$: $$xyyz = (ab)^{3n+j} \mid (ab)^{... • 21 0 votes 0 answers 21 views ### Trying to disprove that if Prefix(L) is regular then L is regular I've thought of using L={a^{2^n}, \forall n \in \mathbb{N}} and then prefix(L)=\Sigma ^{*}. which we know \Sigma^{*} is regular. however, L is not regular. is this a correct solution? • 389 1 vote 0 answers 84 views ### Given an arbitrary language L is there an algorithm that terminates and decides whether the language is regular or not? [closed] I have an arbitrary language L (with finite amount of symbols k), assume the language can be represented in finite space as an input, you can also assume that we can check for w\in\Sigma^* ... 3 votes 2 answers 142 views ### How to show that only this regular expression solves this equation Consider the equation x=v\cdot x + w where x is a variable regular expression, v, w are fixed regular expressions, v has no variables inside it, and w has no x inside it. It is easy to ... 0 votes 1 answer 58 views ### Concatenation of languages - Basics Just trying to understand a homework problem in my theory of computation class: L_1 = (a^nb^n: n > 0) and L_2 = (c^n: n > 0) List the concatenation of L_1L_2 where n = 2. I can find lots ... 0 votes 1 answer 62 views ### How to get words that belong to the language of this regular expression and four which do not, ((a|baa) ∗ (b|ab))∗ . In the alphabet {a, b} for both automata and regular expressions, what would be four words that belong to the language of this regular expression and four which do not, regular expression = ((a|baa)∗(... -1 votes 1 answer 42 views ### Prove a class of regular languages is not closed under a weird concatenation operation [closed] Let's say we have an operation L and a language S. L(S) = \{s^n ~|~ s \in S, n \geq 0\}. How can I prove a class of regular languages is not closed under this operation? 1 vote 1 answer 69 views ### Is the Language L = \{a^n b^m c^k d^q e^r \,|\, n, m, k, q, r \geq 0\} a Valid Regular Language? I am inquiring about the nature of language L. It appears that L is not categorized as a regular language due to its unique characteristics, which involve the need to count occurrences of multiple ... • 388 0 votes 0 answers 50 views ### Regular Expression for the set of all binary strings that are of even length with at most 2 zeros I asked the converse just recently. But now trying to understand this version.. I'm working with case work and then I will take the union of all three cases where its strings with no zeros, 1 zero, ... 0 votes 1 answer 480 views ### Regular Expression for the set of all binary strings that are of even length with at least 1 zero Also followup question is the set of all binary strings that are of even length with at least two zeros. But for both questions I'm thinking of building my regular expression with casework, no zeroes, ... 1 vote 1 answer 162 views ### Let L be a regular language. Prove that L_1, the language created by removing all characters in odd places in all words of L, is regular Let L be a regular language. Prove that L_1, the language created by removing all characters in odd places in all words of L, is regular. Completely stuck on this one. I tried building DFA,NFA,... 2 votes 2 answers 83 views ### Prove that if M is regular then sandwiched M is regular as well Hi I'm having some confusion with regular languages and DFAs. Let's say we have some language M defined as M = \{11, 1010\}. Then let's define some M[0] be defined formally as \{x_10x_2...0x_n | ... 0 votes 1 answer 56 views ### Generating functions of ambiguous regular languages are still rational? The Chomsky-Schützenberger theorem states that any context-free unambiguous language admits an algebraic generating function. For unambiguous regular languages, the generating function is always ... 0 votes 1 answer 55 views ### Is there a name for the set of single-character prefixes of words in a regular language This question concerns regular languages and regular expressions. Suppose we have an alphabet \Sigma and a language \mathcal{L}. For some algorithm, I am particularly concerned with the set of ... • 1 1 vote 1 answer 49 views ### Computer Science: regular languages Is it possible to prove with pumping lemma that the languge$$L=\{w_1w_2 \mid w_1,w_2\in\{a,b,c\}^* \text{ and } \#_a(w_1)>\#_b(w_1) \text{ and } \#_b(w_2)>\#_c(w_2)\}$$(where \#_x(w) is the ... 0 votes 1 answer 63 views ### Find all strings of w that satisfy following equation Solve the following string equation on the alphabet A = \{1, 0\} and find all w's: w011 = 011w 1 vote 0 answers 73 views ### Can substrings of a regular language always be recognized by an "isolated" path in some finite state automaton? I believe I have found a proof of the question I originally asked (see crossed out paragraph), but I have realized that what I actually need to prove is somewhat stronger. What I am actually wondering ... • 787 2 votes 0 answers 80 views ### Are 111^* and 11^*1 equivalent? I know it is a trivial question but are 111^* and 11^*1 equivalent? (I think yes because I can have 11 in both at minimum but that seems odd to be true). I am trying to understand automata theory ... 0 votes 0 answers 55 views ### Regular expression .Find it Construct a regular expression that defines the language of all words that contain either the aa-substring or the bb-substring but NOT BOTH the aa-substring and the bb-substring in the same word.... -2 votes 2 answers 122 views ### Regular expressions creating language m Construct a regular expression that defines the language M (say) containing all words beginning with exactly one a or exactly one b. (Words in M are at least of length 1 and words such as aa, bbbaba ... 1 vote 0 answers 67 views ### Let 𝐿 be a regular language. Prove all minimal automata for the language are isomorphic I have started to study formal languages, especially finite automata and regular languages and I encountered some difficulties, i.e. Is this true: Automata will be called isomorphic if, by changing ... 2 votes 0 answers 84 views ### Prove that L = {w∈{a,b,c}^*|w contains "abc"} is regular with Nerode theorem? How to prove that L = \{w \in \{a,b,c\}^* \mid w \text{ contains } abc \} is regular using the Nerode theorem? Attempt If I show that there are a finite number of equivalence classes for this ... • 53 0 votes 1 answer 62 views ### Prove or disprove that L = {a^nb^m | m ≠ 3n + 5} is a regular How can I prove or disprove that L = \lbrace a^nb^m | m ≠ 3n + 5 \rbrace is a regular language? Attempt Assume L is regular, then its complement L^\complement is also regular. L^\complement ... • 53 0 votes 1 answer 99 views ### Is the following language is regular, context free, and/or decidable? Given a language determine if it is regular, context free, and/or decidable. No proof needed, but an explanation would be appreciated. A = {a^n b^(2n+6) | n >= 0} My first guess is no its ... 0 votes 1 answer 71 views ### Is the algorithmic problem for regular languages decidable? I have an algorithmic problem, where I need to build an algorithm and say if the problem is decidable. Here it is: Regular languages L_1, L_2, and L_3 are given by finite automata. Is the ... 1 vote 1 answer 150 views ### How can I determine the language from a DFA? I was given three DFAs to solve. I understand the first one is a*. I think the second one would be b*(a+)*. I cannot figure out what the third one would be, it seems like there are too many different ... • 11 1 vote 1 answer 80 views ### Prove equivalence of two regex using basic identities. I'm trying to prove the following identity$$ (x+y)^* = (x^*y)^*x^* = x^*(yx^*)^*$$Using the following 12 identities$L + M = M + L(L + M) + N = L + (M + N)(LM)N = L(MN)\emptyset + L = L + ...
1 vote
I am reading "Introduction to the Theory of Computation 3rd Edition" by Michael Sipser. Pumping lemma is the following proposition: THEOREM 1.70 Pumping lemma If $A$ is a regular language, ...
Took a Theory of Computation exam where one of the questions was : Is there an infinite amount of regular expressions for the language $L=\{aa,bb\}$ ? The proof requested was just an informal one. My ...