Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
4
votes
2answers
1k views

Is the language 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
64 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
59 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
15 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
40 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
24 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
68 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
35 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
30 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
45 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
39 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
32 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
49 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
60 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
76 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
100 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
58 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
34 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
33 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
128 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
37 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
22 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
25 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
32 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
80 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
38 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
54 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
26 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
41 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
189 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
73 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
47 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
42 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
29 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
2answers
74 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 ...

1
2 3 4 5
31