Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,559
questions
-2
votes
0answers
19 views
Prove that the following languages are not regular by providing a fooling set
Prove that the following languages are not regular by providing a fooling set. You need to
provide an infinite set and also prove that it is a valid fooling set for the given language
-1
votes
0answers
35 views
A formal proof of Arden's Theorem [duplicate]
I have been searching internet for a correct proof of Arden's Theorem and have searched some book also. Many proofs seem to be completely wrong, filled with fallacies and can't trust what is written ...
0
votes
1answer
42 views
Simplifying the Language of this DFA
Above's the DFA in question (Sipser, Page 36). I have obtained the language of this DFA to be 0*1(1+00+01)*. But Sipser's textbook goes on to explain that the language of this DFA is (0+1)*1(00)*. But ...
2
votes
1answer
50 views
Implication of the Pumping lemma
I'm reading Hopcroft and Ullman's '79 edition of "Introduction to Automata theory, Languages, and Computation". In chapter 3, the authors say "The lemma[sic] does not state that every ...
1
vote
2answers
55 views
Can a non-deterministic finite automaton die out before reading the entire string?
I am new to automata theory and have a problem that I want to solve. We have to design an NFA that starts with "ab". I have the solution and it is given by:
However, my problem is:
If the ...
2
votes
2answers
88 views
Why {${xww|x,w∈(a+b)^*}$} is regular but {${ww|w∈(a+b)^*}$} is not $? $
I read this site example 12 that {${xww|x,w∈(a+b)^*}$} the set of strings generated by language $L$ is {${ϵ,a,b,aa,ab,ba,bb,aaa,…}$} by taking always $w$ as $\epsilon$ and $x$∈$(a+b)^∗$. But my ...
2
votes
0answers
43 views
Intuition for the reason this language which has equal number of 01 and 10 as substrings can be accepted using bounded finite states
Firstly I don't have CS or DFA/NFA background knowledge about their theorems or lemmas, so I don't understand some related questions' answers like here. However, I can easily intuitively understand a ...
0
votes
0answers
34 views
Is my regular expression correct for this question?
IBM has decided that all sequences of numbers (such as mobile numbers) must be ordered in such a way that any mobile number is followed by at least 2 corporate numbers, and any landline number is ...
-1
votes
1answer
28 views
High Level description of Turing Machines
How can create a Turing machine that checks whether or not an input string is a well-defined regular expression? For example, it recognizes a language that consists of string over {0,1} and the ...
0
votes
0answers
52 views
Are the regular expressions equivalent?
Is the following equivalence true?
$$(r_1^*r_2^*)^* = (r_1 + r_2)^*$$
I think these are equivalent since both the expressions generate the same strings: $\{\epsilon,r_1,r_2,\dots\}$ etc.
4
votes
2answers
217 views
Why are Regular sets not closed under infinite unions and intersections? [duplicate]
Why are Regular sets not closed under infinite unions and intersections, with my flawled reasoning I came to a conclusion that since infinite unions can have no relationship between strings of a ...
-1
votes
2answers
47 views
Are this languages can be represented by regular expressions?
The set of all words with the same number of 0’s and 1’s.
The set of all words contained in {0,1}* that have an even number of 0’s and an odd number of 1’s.
I guess first one is NO.
Second one seems ...
-1
votes
1answer
46 views
How to determine whether this language is regular?
I've encountered this question recently: Given $\Sigma=\{\sigma_1, \sigma_2, ..., \sigma_n\}$ and $n\ge 2$, determine whether the following language is regular or not:
$$
L_1=\{w\in\Sigma^*|for \ 1 \...
4
votes
2answers
2k views
Is $\{w_1xw_2\mid w_1,w_2\in \{a,b\}^* \text{ and } x \in \{a,b\}\}$ regular or not?
The language given is $L = \{w_1xw_2\mid w_1,w_2\in \{a,b\}^* \text{ and } x \in \{a,b\}\}$. Is this language regular or not?
Since there is no pattern, so it should be non-regular?
Kindly help!
1
vote
2answers
67 views
prove/disprove regularity of languages
Let $L_1 \in REG$ and $L_2 \notin REG$ prove or disprove:
$\forall L_1 ,L_2 \text{ } $ $\text{ }L_1^C \cup L_2\in REG \lor L_2\setminus L_1\in REG$
I think that it may be disproved,
but I found it ...
-1
votes
2answers
61 views
Is this grammar well-defined? How do I prove the language generated by it is regular?
I have the following problem statement:
Is G well-defined here? I am unsure of this since there's no production rule for $X, Y, Z$, and this confuses me a bit.
And secondly, how do I prove $L$ is ...
0
votes
1answer
16 views
Complementary language of $L\notin RE,coRE$
I mean if $L'$ defined as $L'=\overline{L}$, when $L\notin RE,coRE$.
From the logic point of view it should be $L'\in RE \cup coRE$, isn't?
But it's not make sense for me, where am I wrong?
0
votes
1answer
43 views
How to check $L$ is regular or not [duplicate]
If $L=\{w \in \Sigma^*\mid w=uv,\text{ number of occurnce a's in $u$ equal to number of occurrence b's in $v$}\}.$
I think $L=\Sigma^*$ because for any string in $\Sigma^*$, we can split it to $uv$ ...
2
votes
1answer
27 views
Minimal state DFAs for a regular expression of length $n$
I know that given any regular expression, we can find always find a minimal DFA which accepts the language it describes. However, this process can take up to exponential time and space. I'm wondering ...
0
votes
1answer
72 views
Simplify $R:=0^*+0^*1\left(1+000^*1\right)^*0^*$
I'm trying to simplify the following REGEX:
$$R:=0^*+0^*1\left(1+000^*1\right)^*0^*$$
$R$ is the result of transforming a GNFA that recognizes $L:= \{w \in \{0,1\}^* | \left(\forall \ i \in \left[1,|w|...
0
votes
1answer
41 views
Prove $(aa^*bb^*)^*=ϵ+a(a+b)^*b$ using regex laws
I tried to prove this by starting at RHS:
$$ϵ+a(a+b)^*b = ϵ+a(a^*b^*)^*b$$
But I dont know how to convert $(a^*b^*)^*$ to something else that will be helpful.
Any ideas?
1
vote
0answers
30 views
Prove regularity of $L$ implies regularity of $\widetilde{L} := \{xy \mid xxy \in L\}$
Let $\Sigma = \{a, b\}$. For every language $L \subseteq \Sigma^*$ we denote
$\widetilde{L} := \{xy \mid xxy\in L\}$. Prove that if $L$ is regular, then so is $\widetilde{L}$.
I tried playing around ...
-1
votes
1answer
31 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.
1
vote
1answer
55 views
Is $(L_1^c \cup L_2^c)^c$ context-free or context-sensitive
I came across the following question:
Let $L_1$ be a regular language and $L_2$ be a context-free language. Let $L_1^c$ and $L_2^c$ be their complements respectively. What can be said about $(L_1^c \...
3
votes
1answer
48 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
40 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
33 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
24 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
50 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
37 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
38 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
15 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
63 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
37 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
78 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
30 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
102 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
33 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
62 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
130 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
35 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
34 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
38 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
143 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
38 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
25 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
26 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
42 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
40 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 ...
