Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [regular-languages]

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

1
vote
2answers
58 views

Prove or disprove L is regular

There is question in one of my exercise but I couldn't prove or disprove anything about it. This is language $L$ which is introduced with grammar: $$S \to 0S1 | 1S0 | AA$$ $$A \to 0A | \lambda|A1$$ ...
-1
votes
1answer
17 views

Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$

Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$ sigma is any alphabet. R is a regular expression. How can L(RR) even be a subset or equal to L(R)?
2
votes
1answer
69 views

What is the regular expression for the following language?

What is the regular expression for the following language? $$L = \{acbc: a,b,c \in \{0,1\}^+ \}$$ maybe we can say $$L = ((0 + 1)^+ 0 (0 + 1)^+ 0) + ((0 + 1)^+ 1 (0 + 1)^+ 1)$$ Is it true??
0
votes
2answers
44 views

Formal algorithm to test whether two given regular expressions define equal/identical or unequal languages

I'm trying to create a formal algorithm in order to determine whether two given regular expressions $a$, $a'$ define identical/equal or unequal languages and if those languages are subsets of each ...
2
votes
1answer
60 views

Is SAT known to be non-context-free or even non-regular?

We have seen various languages proven to be outside of REG and CFL by corresponding pumping lemmas. Has something similar been done for SAT?
2
votes
2answers
86 views

Prove regular languages are closed under $f(n) = 2^n$ and $ f(n) = n^2$

Suppose $ R $ is a regular language, let $ f(R) = \{ w | $ $ \exists x \text{ such that } |x| = f(|w|) \land wx \in R\}$, prove that $ f(R) $ is regular for $ f(n) = 2^n $ and for $ f(n) = n^2$. I've ...
1
vote
1answer
89 views

The reverse DFA is not working as expected

Assume a regular language contains all the strings that are ended with "01". We can draw the following DFA for it: And I reversed the DFA according to this answer (designing a DFA and the reverse of ...
-1
votes
2answers
71 views

Several simple propositions about regular languages

(Originally posted on Math-Stackexchange) https://math.stackexchange.com/questions/2982949/regular-languages-and-regular-expressions Notation: $\Sigma:=\{a_1,\cdots ,a_\Delta\}$ finite alphabet $\...
0
votes
1answer
153 views

Using pumping lemma to prove $L2 = \{a^ib^j |i > j \}$ non-regular

I'm having issues using the pumping lemma to prove $L2 = \{a^ib^j |i > j \}$ is non-regular. It's obvious to know that the language is non-regular as there is no way of tracking $a^{i's}$ and $b^{...
1
vote
1answer
58 views

How to show that the language made up of strings with nlogn 0s is not regular with the pumping lemma?

How to show that the following language is not regular with the pumping lemma? $$L=\left\{0^{n\lceil\log_2 n\rceil} \,\middle|\, n\in \mathbb{N}-\{0\}\right\}.$$
-1
votes
1answer
41 views

Proving a language is non-regular using the Pumping Lemma for non-binary strings [duplicate]

I am unsure of how to prove this language is non-regular. I do not even know where to start to develop a string that would prove the language is non-regular by contradiction. Any help would be ...
0
votes
1answer
38 views

Can this DFA be converted to a regular expression? [duplicate]

I want to make the regular expression of this language but I can't: I tried but the regular expression didn't match some strings that it should. Is it even possible?
1
vote
1answer
21 views

Describing the Language of a grammar in set theoretic notation where the length of strings need to be remembered

I am not well versed in this topic so please pardon any ambiguous notation. I am trying to describe the language of this grammar in set-theoretic notation. The Grammar is given by: $ S \rightarrow ...
1
vote
1answer
49 views

Designing a context free grammar for a language; When to use the empty string

$L= \{a^{2i}b^{j}vc^{j}(ac)^{i} | i,j \ge 0, v \in \{a,b\}^*\}$ over the alphabet $\Sigma = \{a,b,c\}$ How can a grammar be created from the language without the use of the empty string. Below is my ...
3
votes
3answers
130 views

Is the power of a regular language regular? Is the root of a regular language regular?

If $A$ is a regular set, then: $L_1=\{x\mid\exists n \geq0, \exists y \in A: y=x^n\}$, $L_2=\{x\mid \exists n \geq0, \exists y\in A: x=y^n\}$. Which one of them is regular? My reasoning is since ...
1
vote
1answer
168 views

Proving $L = \{a^nb^m \mid n, m≥0, n \neq m\}$ is not regular by use of Pumping Lemma

I've been struggling with this problem for quite a while now and every explanation I have managed to find doesn't seem to correctly solve it. Question Proving $L = \{a^nb^m \mid n, m≥0, n \neq m\}$...
1
vote
3answers
157 views

Is there a *simple* proof that the intersection of a CFL and a regular language is a CFL?

I am following a course on complexity theory where languages are a part of the course. There is a proof that no matter how hard I try to understand, it is till so complex that I cannot make it to half ...
-1
votes
1answer
75 views

Can there exist two minimal dfa for same regular language?

As said the answer is pretty simple "no", but that is not what i encountered. Here is the summary : i took a regular language , produced two ways of accepting same language (the ways in my ...
1
vote
1answer
60 views

Find the number of strings in the language $(∅∅^∗ + ∅)$

Consider the language $L = \emptyset\emptyset^∗ + \emptyset$. How many words does $L$ contain? Zero or one? Note: $\emptyset^∗ =\{\epsilon\}$.
0
votes
1answer
151 views

If a language has a regular grammar, is it regular?

If L has a regular grammar, is L always a regular language? A regular grammar is a formal grammar that is right-regular or left-regular. Every regular grammar describes a regular language. So would ...
1
vote
1answer
71 views

Find equivalence classes of language $L = \{0^n1^n, n \in \mathrm{N}_0 \}$

I'm asked to find all equivalence classes of the language $$L = \{0^n1^n, n \in \mathrm{N}_0 \}$$ We have the following definition: $$(xR_Ly)\Leftrightarrow (\forall w\in \Sigma^* xw\in L \...
2
votes
1answer
147 views

Regularity of language of words containing a square

$$L = \{w\mid w\text{ contains a substring of form }yy\text{, where }y\text{ is any non-empty string}\}.$$ Is this language regular? We do not know what $y$ looks like in advance. And why is this ...
0
votes
1answer
64 views

Why does removing all copies of a letter preserve regularity?

Let $P(a,L)$ remove every $a$ in $L$, for example $$ P(a,\{ab,aab,aaab,bba\}) = \{b,bb\}. $$ How to show that if $L$ is a regular language then $P(a, L)$ is also a regular language? My attempt: If $...
0
votes
2answers
41 views

How to deal with character set in regular expression?

In regular expression implemented by language like perl or python, user can write a set of characters like [123abcd] or special notation like \d to represents digit ...
3
votes
1answer
86 views

Find a regular grammar that generates words with even number of a's

I have a language $L$ = {$vabu$ | $v$,$u\in \{a,b\}^*$, $|vu|_a = 0$ $($mod $2)$$\}$ where $|vu|_a$ is number of $a$ in $vu$. I came up with these rules: $\sigma \rightarrow aa\sigma | ab\xi$ $\...
1
vote
1answer
43 views

Is my pumping lemma proof correct? [duplicate]

Show that $L = \{a^nb^l \ | \ n \leq l \}$ is not regular I'd like to check if my proof for this is correct. Proof: Choose any positive integer $m$. Pick $w = a^mb^{m+1} \in L$. Note that $|w| = 2m+...
6
votes
3answers
2k views

Prove that A** = A*, where A is a language over Σ*

Let $\mathcal A$ be an arbitrary language over $\Sigma^*$ Proof. To prove, $\mathcal A^{**} = \mathcal A^* $ $\mathcal A^{**} = \left( \mathcal A^0 \cup \mathcal A^1 \cup {...} \cup \mathcal A^n \...
0
votes
2answers
166 views

Non-regular language whose prefix language is regular

I understand that prefix of a regular language is regular, but I am unable to get my head around this: Give an example of a non-regular language $A ⊆ \{0, 1\}^*$ for which $\operatorname{Prefix}(A)$...
-1
votes
1answer
143 views

What is an infinite language?

I just started reading about formal language theory and what i have learnt so far that: Alphabet is a finite set of symbols. String/Word: is always finite. Because a language is set of strings of ...
3
votes
3answers
123 views

If $L$ is a regular language, then $s(L)$ is also regular

...where $s$ is a substitution that replaces each symbol of each string in $L$ with a regular expression. For example, if $L=a^*b$ and $s(a) =ab, s(b) = b^*$, we have $s(L) = (ab)^*b^*$. My ...
0
votes
2answers
127 views

How does modulus affect the regularity of language?

the question is as follows, further the notation used are standard as used in theory of computation $$L = \big\{ w : w \in \{a,b\}^*,\ |n(a) - n(b)| = 2k\}\,.$$ Beware 'K' is not a fixed integer its ...
0
votes
3answers
711 views

is this language regular and why pumping lemma doesn't work?

I was told that this language is regular but as I can show below, pumping lemma is not working for it. What am I doing wrong? Is this language really regular? Why?
0
votes
1answer
111 views

Trying to simplify a particular regular expression

The question is as follows $$(a^* (ba)^* )^* (b+\epsilon) = (a+b)^* (b+\epsilon)\,.$$ But I am unable to solve this regex expression. My answer is as follows: \begin{alignat*}{2} (a^* + (ba)^* )^...
0
votes
2answers
75 views

Does there exists a finite automata for the given language?

The question is simple and given as, $alphabets=\{a, b\}$, and language $L$ over them as: $L = \{w: w \ € \{a, b\}^*, (n(a) - n(b)) \ mod \ 3=1\}$. Here $n(a)$ = number of $a$ and $n(b)$ is number of ...
1
vote
1answer
42 views

Proving irregularity of $\{a^nb^k \mid n > k \text{ or } n \neq k-1\}$

I need help with proving the following language is not regular: $$ L = \{ a^n b^k \mid n > k \} \cup \{ a^n b^k \mid n \neq k-1 \} $$ My usual methods using pumping lemma are not getting me ...
2
votes
1answer
105 views

Closure of regular languages under deleting a 1 from each even run of 1s

Let $R$ be a regular set over the alphabet $\{0, 1\}$. Give a machine construction to prove that the set obtained by deleting one 1 from each even length block of 1’s is also regular, and using ...
1
vote
1answer
149 views

Can we prove using pumping lemma that language F = {$a^ i b ^j c ^k$ | i, j, k ≥ 0 and if i = 1 then j = k} is not regular?

I am currently solving a problem in which we have to show that we can not prove using pumping lemma that the language mentioned in the question is not regular.Here is the full question Consider the ...
3
votes
1answer
32 views

Given the regular set $S = a^*ba^*ba^*$, is the set $S'$ of all first thirds of strings in S (with length divisible by 3) regular?

I have no idea how to approach this problem, could I get at least a hint on how to go about proving/disproving this? I've tried the pumping lemma but I don't think it applies here. I've also tried ...
4
votes
1answer
148 views

Efficiently convert an NFA with multiple $\varepsilon$ edges and accepting states into a regular expression

Given an NFA with alphabet $\Sigma = \{a, b, c\}$ defined in the diagram, is there a way to efficiently convert it into a regular expression? The way I solved this problem is to first convert the NFA ...
6
votes
2answers
380 views

Find the language an NFA recognizes

For example, I have an NFA $A_n$ with alphabet $\Sigma = \{0, 1\}$. The language recognized by this NFA is known to be $\{u1v\ |\ u, v \in \Sigma^*, |v| = n − 1\}$. I was unable to get the ...
2
votes
2answers
92 views

Finding if the given language is regular or not

I have the language $$L = \{a^mb^nc^o| \, m + n + o > 5\}$$ where $m,n,o$ are non-negative integers. I have to find whether the language is regular or not. My attempt: I feel it should be non ...
0
votes
1answer
21 views

Choose the best classifier to predict the label of strings of a regular language

I have to tackle this problem: I have some strings that are my training set. These strings belong to a regular language corresponding to a deterministic finite automata (hidden namely I don't now it, ...
2
votes
1answer
48 views

Regular expression for capturing a “C-style” string

I have started to learn automata theory and languages. I am new to regular expressions. As a use case in real world, I would like to construct a regular expression to accept a c-style string: ...
1
vote
2answers
184 views

Is every regular/context free langauge decidable in LogSpace?

I know all the regular languages are decidable but not sure whether it can be done in LogSpace.
1
vote
1answer
71 views

Is the language $K=\{u \in\{0,1\}^n\mid n \geq 0, \forall_{v \in\{0,1\}^n} (u+v) \in L \}$ regular?

For two words $w,v \in\{0,1\}^*$ of equal length, let $w+v \in\{0,1,2\}^*$ denote the word in which the $i$-th word is the sum of $i$-th position of $w$ and $v$, as follows: if $w=a_1 \ldots a_n$ and $...
-1
votes
1answer
106 views

How to convert a CFL to a deterministic PDA?

I am trying to complete this question. However, I am unsure of the steps necessary to complete the conversion from a CFL to a deterministic PDA. I know that $ww' | w \in \left \{ a,b \right \}^{*}, w'...
3
votes
2answers
48 views

Question about mapping reducibility

I am working on an assignment where one of the sub questions is: Let $A$ and $B$ be languages. Suppose $A$ is context free and $A ≤_m B$, which means that there is a computable function $f\colon \...
3
votes
2answers
360 views

Is DFA and Regular Expression equivalent?

The language of a DFA can be the empty set (by defining no final states), but can a Regular Expression do that? If Regular Expression cannot do that, does it mean that DFA and Regular Expression are ...
6
votes
3answers
2k views

How to prove using pumping lemma that language generated by a(b*)c(d*)e is regular?

I am studying pumping lemma from Introduction to theory of computation by Michael Sipser. I wanted to check if the language generated by regular expression ...
1
vote
1answer
27 views

Minimum number of letters

I have an assignment that I have to do and the question is Draw a DPDA that accepts the language L = {ba(bb)^(n+1)a^(n – 1) |n > 1}. Im not looking for the answer but rather some direction. I ...