Questions tagged [regular-languages]

Questions about properties of the class of regular languages and individual languages.

Filter by
Sorted by
Tagged with
-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,...

1
2 3 4 5
31