Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
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 ...
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?...
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?
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) ...
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 ...
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 \...
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 ...
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 ...
-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 ...
-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 ...
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 ...
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 ...
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 \} $$ ...
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 ...
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?
-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: ...
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 ...
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 ...
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 ...
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 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 ...
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.
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 ...
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 ...
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 =...
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^{...
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. ...
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 ...
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 ...
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 ...
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$$
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\}$....
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)^*$: \...
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+...
-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 ...
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 ...
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 &...
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 ...
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 ...
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 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 ...
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 ...
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 ...
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 ...
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 \\ ...
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 ...
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 ...
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 ...

1
3 4
5
6 7
34