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
1
vote
1
answer
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
2
votes
0
answers
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\}$...
- 21
3
votes
1
answer
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
0
answers
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
0
votes
0
answers
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 ...
0
votes
2
answers
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
1
answer
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
2
votes
0
answers
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 ...
- 783
0
votes
0
answers
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 ...
3
votes
1
answer
37
views
Directly constructing a DFA for the Kleene star of a language given as a DFA?
The regular languages are closed under Kleene star. One common way to prove this is to define a construction that, given a DFA or NFA for a regular language $L$, produces a new NFA whose language is $...
- 10.6k
1
vote
1
answer
71
views
Can a Turing Machine decide if a language is regular, in general?
Can a Turing machine decide/recognize if a given language is regular, in general?
$
REG_{TM}=\{\langle M\rangle|\langle M\rangle \text{ is a TM and }L(M) \text{ is regular}\}
$
I'm pretty confident ...
0
votes
1
answer
51
views
Find the quotient of $L_1$ and $L_2$.
We want to find the quotient of languages $L_1$ and $L_2$.
My question is what happens when the length of a word in $L_2$ is greater than the length of the word in $L_1$, for instance:
$abc$ and $cc$.
...
- 63
0
votes
0
answers
41
views
Regular expression for binary numbers
I need to find regular expression for strings representing binary numbers that are not less than 51.
How can I do that? I can't find any pattern in their binary pepresentation.
- 27
1
vote
1
answer
57
views
Building a DFA/NFA to prove that a language is regular - exercise
I was given the following exercise and am having a hard time coming up with an intuition for it.
Given a regular language $L$ on the alphabet $\Sigma$, prove that the following language is regular by ...
- 463
2
votes
1
answer
76
views
How to prove $\{0,1\}^*$ equals $\{1\}^* (\{0\}\{0\}^*\{1\}\{1\}^*)^*\{0\}^*$
Consider the set of all binary strings which is $\{0, 1\}^∗$
Now I want to prove the following:
(A) Prove that $\{0,1\}^* = \{1\}^* (\{0\}\{0\}^*\{1\}\{1\}^*)^*\{0\}^*$
(B) Prove that the elements of $...
- 121
1
vote
1
answer
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
2
answers
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
1
answer
65
views
Find $L_1$ and $L_2$ (formal languages)
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 ...
- 48
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 ...
user1249385
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 ...
- 9
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)∗(...
user1248046
-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, ...
- 89
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, ...
- 89
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,$...
- 481
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 | ...
- 89
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 ...
- 138
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 ...
- 13
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$
- 11
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 ...
- 21
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 ...
- 95
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 ...
- 13
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 + ...
- 345
1
vote
0
answers
107
views
Is Pumping lemma so useful? (Michael Sipser "Introduction to the Theory of Computation 3rd Edition")
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, ...
- 8,790
1
vote
1
answer
37
views
Infinite number of regular exressions for a given 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 ...
- 27