Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,520
questions
-1
votes
0answers
28 views
How can i show that this particular Language is Irregular?
The question is to show that this language is not regular:
$$L= \{a^n b^k : n > k\} \cup \{a^n b^k : n ≠ k-1\}$$
How does this work? What should I do to prove that this is not regular?
0
votes
0answers
26 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
34 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
76 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
32 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
23 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
33 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
23 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
75 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 \} $$
...
0
votes
1answer
35 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
40 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
18 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
37 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
134 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
49 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
39 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
1answer
26 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
24 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
44 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
43 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
47 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
37 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
51 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
155 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
48 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
52 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$$
3
votes
2answers
395 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\}$....
1
vote
2answers
38 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)^*$:
\...
0
votes
0answers
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+...
-1
votes
1answer
54 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 ...
3
votes
2answers
583 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 ...
1
vote
1answer
35 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 &...
1
vote
2answers
41 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 ...
1
vote
0answers
51 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 ...
0
votes
1answer
31 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 ...
2
votes
0answers
42 views
In what bases is the language $a^n$ regular?
Given $a\in\mathbb{N}$, I wondered for what bases $b$ is the following language regular
$$\{a_ka_{k-1}\ldots a_0\mid \exists n\in\mathbb{N},\ a_0+a_1b+a_2b^2+\ldots+a_kb^k=a^n\}$$
I think it's regular ...
1
vote
1answer
30 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 ...
0
votes
0answers
20 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
vote
2answers
45 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 ...
2
votes
0answers
51 views
Regular expression vs rational expression
Let $M$ be a monoid (e.g. $M = \Sigma^*$) and $L \subseteq M$.
Then $\mathsf{RAT}(M)$ is the set of rational sets of $M$ and the elements of $\mathsf{RAT}(M)$ are inductively defined as follows:
$|L| ...
1
vote
1answer
59 views
Construct a grammar for $\{a^n(bc)^m : m,n \ge 1, m < n/2\}$
I'm new to writing languages in context-free or regular grammar, so I'm struggling how to do this one. It is a bit more complicated that simpler ones I've practiced doing. The problem is to construct ...
1
vote
0answers
23 views
The purpose of the splitting lemma for $\mathsf{SF(\Sigma^*})$
We've definied the splitting lemma for starfree languages as follows:
Let $L \in \mathsf{SF}(\Sigma^*)$ and $A, B \subseteq \Sigma$ with $A \cap B = \emptyset$. Then it holds true that for $K_i, L_i \...
0
votes
1answer
68 views
Is the following language regular; context-free but not regular; or not context-free?
Let $\Sigma=\{0, 1, \#\}$.
Is the following language regular; context-free but not regular; or not context-free?
Justify your answer
$$L=\{x\#y :\ x, y \in\{0, 1\}^∗\text{ and }\operatorname{bin}(x) + ...
1
vote
1answer
57 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 ...
0
votes
0answers
18 views
Fixing changing characters a regular expression [duplicate]
I have a regular language $L$ from characters of $\Sigma_1$, we define: $\Sigma_2=\Sigma_1\cup \{+,-\}$ and
$$L^{+-}=\left\{a_1\cdot p\cdot a_2\cdot q \cdot a_3\cdot\ldots \cdot a_k\mid a_1,a_2\ldots,...
