Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,663
questions
2
votes
1
answer
9k
views
Why is the complement of a language that is not regular also not regular?
In my lecture notes I we were given two languages and were shown that each of the two languages were not regular. The second was the complement of the first language. To show the second was not ...
- 163
0
votes
3
answers
205
views
How many languages are described by a regular expression?
How many languages can a Regular Expression describe is it only one or infinite?
I have tried to google it but i haven't found any answer?
I know that a Regular Expression describes a Regular Language?...
- 269k
2
votes
1
answer
76
views
If $\{ww^R \mid w \in L\}$ is regular, is $L$ itself regular?
If $L$ is some language and
$\{ww^R \mid w \in L\}$
is a regular language then does $L$ have to be a regular language?
- 269k
4
votes
1
answer
3k
views
Understanding application of Arden's theorem to find regular expression
I learnt Ardens theorem and its usage as follows:
Ardens Theorem
Let $P$ and $Q$ be two regular expressions over alphabet $Σ$. If $P$
does not contain null string, then $R = Q + RP$ has a ...
1
vote
0
answers
46
views
What is the connection between finite automata and logic (sequential calculus)?
Languages recognized by finite automata are exactly those definable
by sentences of the sequential calculus, and also exactly those
definable by rational expressions (also called regular expressions)
...
- 287
2
votes
4
answers
395
views
Proving that $L=\{ w \mid \lvert w \rvert$ is prime $\}$* is a regular language
I'm trying to prove that the following languague is a regular language:
$L=\{ w \mid \lvert w \rvert$ is prime $\}$*
What I have thought is to divide each word $w \in L$ into subwords of length 2 if ...
- 5,925
1
vote
1
answer
48
views
Create a CFG for $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $
I'm trying to find a CFG for the following language:
$L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $
What I thought about unsuccessfully is the following:
$S \rightarrow SASBS \mid SBSAS \mid \...
- 269k
1
vote
1
answer
37
views
Using pumping lemma to prove that $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $ is irregular
Given the following language:
$L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $
I am trying to prove that it is not regular. On the one hand my intuition tells me that the language is non-regular as ...
- 269k
1
vote
2
answers
33
views
Proving Irregularity of $L = \{ a^mb^nb^n \mid nm \ge 3 \} $
I'm trying to prove the irregularity of the following language:
$$L = \{ a^mb^nb^n \mid nm \ge 3 \} $$
I tried to demonstrate that it doesn't verifies the Pumping Lemma but for all words I tried it ...
- 269k
-2
votes
1
answer
173
views
Regular expression for binary representation of even numbers?
I need help writing the regular expression over the alphabet (0,1) represent the even numbers in base ten. So basically the regular expression would show represent an even number in binary. (also if ...
D.W.♦
- 140k
-1
votes
1
answer
41
views
Prove that given 2 regular expressions represent the same language
Is it possible to use regular expression identities to prove or disprove that the RE1=0*(0+1)*0* and RE2=(0+1)* represent the ...
- 10.7k
1
vote
1
answer
248
views
Is the language of words having same number of a's and b's context-free?
I'm trying to use the pumping lemma, to show that the language $$L = \{w \in \{a, b\}^+: na(w) = nb(w)\}$$ is not context free, where $na(w)$ is the number of $a$'s in $w$ and $nb(w)$ is the number of ...
- 33k
3
votes
2
answers
214
views
Infinite prefix-closed context-free languages contain an infinite regular subset
The Problem:
Say that a language is prefix-closed if all prefixes of every string
in the language are also in the language. Let C be an infinite,
prefix-closed, context-free language. Show that C ...
- 2,279
0
votes
0
answers
93
views
Convert the Finite Automata (FSA) into its equivalent regular expression, using stepwise minimization
I was doing an assignment of Theory of automata but while doing this question I am stuck there is no such state that can be eliminated even from transition table. I am very confused and stuck please ...
2
votes
1
answer
87
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 \} $$
...
- 10.7k
1
vote
1
answer
68
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 ...
- 43
1
vote
1
answer
95
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?
- 269k
-1
votes
2
answers
75
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:
...
- 24.9k
0
votes
0
answers
116
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 ...
- 147
0
votes
0
answers
25
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 ...
- 103
1
vote
2
answers
309
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 ...
- 43
1
vote
2
answers
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? ...
- 1
1
vote
2
answers
114
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 ...
- 33k
0
votes
1
answer
53
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.
- 269k
1
vote
2
answers
148
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 ...
- 269k
1
vote
0
answers
54
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 ...
- 11
0
votes
1
answer
64
views
Is the language $\{a^n b^m : 1000|nm \}$ regular?
We have a language $$ L = \{a^n b^m \mid 1000|nm \} $$
Is this language regular?
I'm trying to disprove this using the Pumping Lemma, but it didn't work.
assume I say $x=a^{h}$ and $y=a^{t}$ and $z =...
- 22.7k
0
votes
1
answer
66
views
Is the language $\{a^n b^m \mid 2n + 3m \le 1000 \}$ regular?
We have a language $$ L = \{a^n b^m \mid 2n + 3m \le 1000 \} $$
Is this language regular?
I'm trying to disprove this using the Pumping Lemma, but it didn't work.
assume I say x = $x=a^{h}$ and $y=a^{...
- 22.7k
7
votes
2
answers
173
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. ...
- 101
2
votes
1
answer
56
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 ...
- 269k
1
vote
1
answer
56
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 ...
- 269k
2
votes
1
answer
97
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 ...
- 7,127
2
votes
1
answer
63
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$$
D.W.♦
- 140k
3
votes
2
answers
429
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\}$....
- 269k
1
vote
2
answers
162
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)^*$:
\...
- 269k
0
votes
0
answers
25
views
Is this a regular language + context free [duplicate]
Is $L_1 = \{0^n1^m0^{n+m}\mid m,n \geq 0\}$ regular? What is its context free grammar and proof?
Second, is the following language context-free?
$$L_2=\{0^a1^b2^c \mid a,b,c \geq 0 \text{ and } c = ab+...
- 269k
-1
votes
1
answer
66
views
Is this language a context free language?
Consider the following language, where the alphabet is $\{0, 1, 2\}$:
$B = \{0^a1^b2^c|a, b, c \geq 0 \text{ and }c = ab + 1\}$.
Is this language a context free language? Prove your answer.
I am ...
- 7,127
3
votes
2
answers
1k
views
Given L is a regular language, prove that Perm(L) is Context-Free
Given a regular language $L$ defined over $\Sigma = \{0, 1\}$. We define a new language $$Perm(L) = \{w \mid \exists x \in L, w \in perm(x)\}, $$ where $perm(x)$ is the set of all permutations of the ...
- 27.2k
1
vote
1
answer
191
views
Proving a language with $(ab)^n$ is not regular with pumping lemma?
I have been working to understand the pumping lemma better, but I am quite stuck at proving these two languages is not regular:
\begin{align}
L_1 &= \{(ab)^n c^m \mid n\ge 1, m\ge 2n \} \\
L_2 &...
- 269k
1
vote
0
answers
58
views
Why H-trivial monoids correspond to the variety of aperiodic monoids
I have two similar questions, one about the H-trivial monoids and one about the R-trivial monoids.
I cannot see the reason why H-trivial monoids, i.e., the monoids where H induced classes are ...
- 269k
0
votes
1
answer
55
views
Language of regular grammar
What is the regular grammar of the language: $$L=\left\{a^nb^nc^md^m\left|n,m\ge 1\right|\right\}\:above\:\Sigma =\left\{a,\:b,\:c,\:d\right\}$$
My attempt: $$S\rightarrow aAbcBd|aXd$$ $$A\rightarrow ...
- 14.5k
4
votes
2
answers
122
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
...
- 1,369
1
vote
2
answers
66
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 ...
- 269k
1
vote
2
answers
970
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 ...
- 4,611
0
votes
1
answer
69
views
Regular expression for words longer than 2 containing at most two x-s
I want to make a regular expression for the language consisting of words whose length is at least 3 and which contain at most two $x$'s, that is,
$$\{w\in \{x,y\}^* \mid |w|\geq3\text{ and the number ...
- 269k
1
vote
1
answer
110
views
Regular language where syntactic right congruence and syntactic congruence differ
Find an example of a regular language where the syntactic right congruence and the syntactic congruence are not identical.
I have gone through the relevant definitions and understand them, but could ...
- 269k
2
votes
6
answers
18k
views
Explaining why a grammar is not LL(1)
I need some help with explaining why a grammar is not LL(1).
Let us take the following grammar:
$$
\begin{align}
S \rightarrow & aB \mid bA \mid \varepsilon \\
A \rightarrow & aS \mid bAA \\
...
- 269k
1
vote
1
answer
174
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 ...
- 269k
0
votes
0
answers
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 ...
- 1
4
votes
1
answer
6k
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 ...
- 469