Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,540
questions
-1
votes
1answer
25 views
How to prove that $L = \{w\in\{a,b\}^*\mid w = uav \text{ and } |u| = |v|\}$ is not a regular language
$L = \{w\in\{a,b\}^*\mid w = uav \text{ and } |u| = |v|\}$
I know to use the pump lemma, but I don’t know how to use it correctly.
0
votes
0answers
23 views
Is $(L1^c \cup L2^c)^c$ context-free or context-sensitive
I came across this question "Let $L1$ be a regular language and $L2$ be a context-free language. Let $L1^c$ and $L2^c$ be their complements respectively. What can be said about $(L1^c \cup L2^c)^...
-1
votes
0answers
25 views
How to check whether a language is regular or not? [duplicate]
I am given expressions such as
\begin{align}
L_2 &= \{ a^n b^{n!} \}, \\
L_3 &= \{ abcva^n \mid v \in \{a,b,c\}^*, n \in \mathbb{N}, n \text{ is even}, |v|=n/2 \}.
\end{align}
3
votes
1answer
40 views
Efficient algorithm to find a rejecting input of an NFA
I cannot think of a PTIME algorithm to find a rejecting input of an NFA. While it is possible to efficiently find a rejecting input for a DFA, converting an NFA to DFA is too expensive.
The algorithm ...
1
vote
1answer
37 views
Is the concatenation of a non-regular CFL and a complement of a regular upper-set always non-regular?
Let $L_1$ be a non-regular CFL. Let $L_2$ be a regular language. Assume that $\left(L_1\right)^{*} \subseteq L_2$. I'm looking at $L_3 = \left( L_1 \right) ^{*} \circ \overline{L_2}$. Is $L_3$ always ...
-1
votes
1answer
29 views
How to choose word for pumping lemma for $a^kb^{2k}a^k$?
I have to show that the language $ \mathcal {L} = \{a ^ k b ^ {2k} a ^ k: k \geq 0 \} $ is not a regular language. So that's what I want to use the pumping motto for. What I could do is this: let $ \ ...
2
votes
1answer
22 views
Proving $S=SL\implies S=\emptyset$
Let $L\subseteq \Sigma^*$ such that $\{\epsilon\}\not\in L$. Then for any $S\subseteq \Sigma^*,
S=SL\implies S=\emptyset$.
So we suppose $S=SL$ and $S\ne\emptyset$. Then $\exists w\in S$ such that $...
0
votes
1answer
45 views
Describe regular expression
I am learning about regular expression, and trying to describe a regular expression for the language L
$\qquad L = \{a^i b^j c^k \mid i+j = k\}$
What is the right approach and how to describe a ...
3
votes
1answer
36 views
How does the union of two machines which accept language of form $0^{mx+b}$ look like
I am doing Shai Simonson's course on Theory of computation. I am not able to understand part b of one of its problem sets.
a. Prove that languages of form $0^{mx+b}$, where m and b are positive ...
0
votes
0answers
37 views
Designing CFG that accepts $a^n b^m c^p$ where $n=m+p+2$
I have generated the CFG of $a^n b^m c^p$ where $m = n+p+2$:
$S \rightarrow ASC \mid \varepsilon$
$A \rightarrow aAb \mid \varepsilon$
$C \rightarrow bCc \mid \varepsilon$
I have been trying $a^n b^...
0
votes
1answer
14 views
Regular set corresponding to regular language
I have just started learning regular expressions and I don't have anybody around me to help me building conceptions. So I rely on online mediums. My question is whether every regular set corresponds ...
2
votes
2answers
54 views
Prove the language $\{x \in \Sigma^* : \exists w \in \Sigma^* \ xww \in L \}$ for regular language $L$ is regular
Let $\Sigma=\{0,1\}$ and $L$ be a regular language. Prove that
$$Z(L) = \{x \in \Sigma^* : \exists w \in \Sigma^* \ xww \in L \}$$
is a regular language.
I tried to build a NFA based on the DFA that ...
0
votes
1answer
34 views
Minimum pumping length of finite language
Background
Let L = {aa}. We know that the minimum pumping length of L is |aa| + 1 = 3. For this length all the three conditions of the pumping lemma vacuously hold true.
Doubt
Let L = {aa, aab}. Is it ...
5
votes
1answer
47 views
Can a non-regular language $L$ have a non regular $L^*$?
I have been looking around and i cant seem to find an example of such case that a non-regular $L$ has a non regular $L^*$. Is it possible? If so, can you provide an example of such case please?
-3
votes
1answer
29 views
Prove a language is not regular without pumping lemma [duplicate]
How can you prove that $L=\{a^n b^{2n} \}$ is not regular without the use of pumping lemma?
3
votes
1answer
94 views
NP completeness of deciding whether a set of examples, consisting of strings and states, has a corresponding DFA?
I'm working on a textbook problem, 7.36 in Sipser 3rd edition. It claims that if we are given an integer $N$ and set of pairs $(s_i, q_i)$, where $s_i$ are binary strings and $q_i$ are states (we are ...
1
vote
1answer
30 views
Myhill-Nerode - Prove irregularity for $\{a^{n^3}\}$
I need to prove that the following language is not regular by showing there are infinite pairwise distinct equivalence classes:
$$
L = \{a^{n^3} \mid n \geq 1\} \subseteq \{a\}^*
$$
Looking at a ...
2
votes
1answer
52 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?
0
votes
3answers
129 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?...
0
votes
1answer
33 views
PDA accepting of a specific symmetric language
Assume we have PDA that accepts a specific symmetric language on $\{a,b\}^*$.
if we have $a$ This side of the string, on the other side of the string we have $aa$.
and if we have $b$ This side of the ...
0
votes
0answers
32 views
Prove language is not Turing-recognizable using contradiction
Show that the language L = {<M>| M is a TM and does not accept <M>} is not Turing-recognizable.
Note: Prove by contradiction. No need for reduction.
This is the problem I am trying to ...
1
vote
0answers
37 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)
...
2
votes
4answers
98 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 ...
1
vote
1answer
34 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 \...
1
vote
1answer
21 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 ...
1
vote
2answers
24 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 ...
-1
votes
1answer
31 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 ...
-2
votes
1answer
35 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 ...
0
votes
0answers
28 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
1answer
79 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 \} $$
...
1
vote
1answer
37 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?
1
vote
1answer
50 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 ...
0
votes
0answers
25 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 ...
0
votes
0answers
18 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 ...
-1
votes
2answers
40 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:
...
1
vote
2answers
173 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 ...
2
votes
2answers
71 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 ...
0
votes
1answer
42 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.
0
votes
2answers
41 views
Proving that a language defined by a regular expression is equivalent to a right linear grammar
After thinking for a bit, I am not able to prove a double inclusion proof for the following problem. It seems very interesting to me.
Consider the regular expression $r= ((1(00)^∗1 + 0)1)^∗$ and the ...
2
votes
1answer
26 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. ...
2
votes
1answer
52 views
All words containing at least twice as many zeroes as ones
Consider the language
$$
\{ w \in \{0,1\}^* : \#_0(w) \ge \#_1(w) \}
$$
consisting of all words over $\{0,1\}$ in which the number of zeroes is at least twice the number of ones.
Is this regular, ...
1
vote
0answers
45 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 ...
0
votes
1answer
50 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 =...
0
votes
1answer
38 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^{...
1
vote
2answers
63 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 ...
7
votes
2answers
159 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. ...
1
vote
1answer
34 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 ...
2
votes
1answer
51 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 ...
2
votes
1answer
53 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 ...
2
votes
1answer
54 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$$
