Questions tagged [regular-languages]

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

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

1
2 3 4 5
31