Questions tagged [regular-language]

Regular languages are formal languages which are recognized by a finite automaton. It is equivalently the languages which are expressible as a regular expression. In addition to these two, there are several other equivalent definitions.

Filter by
Sorted by
Tagged with
1 vote
1 answer
49 views

Find $L_1$ and $L_2$ (formal languages)

We have two languages $L_1, L_2 \subseteq \{{a, b}\}^{*}$. According to the following formulas find $L_1$ and $L_2$: $L_1 = \{\lambda\} \cup \{a\}.L_1 \cup \{b\}.L_2 $ $L_2 = \{\lambda\} \cup \{b\}....
winter's user avatar
  • 31
1 vote
2 answers
31 views

Proof of irregularity of a language, L = {0^n : n is prime}

So the above statement is a question from a course on Theory of Computation. I have already proven it using the pumping lemma, but am looking for proofs using the Myhill-Nerode theorem, or more ...
Manu Sankaran's user avatar
2 votes
1 answer
39 views

If $L$ is regular, is $L' = \{xz \mid \exists y, y \in \Sigma^* \text{ such that } |x|=|y|=|z|\text{ and }xyz \in L\}$ regular?

I know how that if the condition $|x|=|y|=|z|$ is relaxed, then we get another regular set, as is shown by the construction in this question or this one. But I am not able to solve for this case when ...
Harsh Choudhary's user avatar
1 vote
1 answer
34 views

Why do we need empty string transitions in the NFA intended to accept this singleton language?

Consider the attached NFA (from Sisper's Introduction to the Theory of Computation, 3e) which has been deduced in order to accept precisely the language containing the string $ab$. The rest of the ...
EE18's user avatar
  • 1,177
0 votes
1 answer
57 views

Is the Language $L=\{(ab)^{3n}\:|\:n\in\mathbb N\}$ regular?

Is the language regular? My application of the pumping lemma suggests: splitting it in $xyz$: $$ x = \emptyset \mid y= (ab)^{j} \mid z=(ab)^{3n-j} $$ Pumping up $y$: $$ xyyz = (ab)^{3n+j} \mid (ab)^{...
Robert's user avatar
  • 21
0 votes
0 answers
11 views

Trying to disprove that if Prefix(L) is regular then L is regular

I've thought of using $L=${$a^{2^n}, \forall n \in \mathbb{N}$} and then $prefix(L)=\Sigma ^{*}$. which we know $\Sigma^{*}$ is regular. however, $L$ is not regular. is this a correct solution?
Aishgadol's user avatar
  • 389
1 vote
0 answers
80 views

Given an arbitrary language L is there an algorithm that terminates and decides whether the language is regular or not? [closed]

I have an arbitrary language $L$ (with finite amount of symbols $k$), assume the language can be represented in finite space as an input, you can also assume that we can check for $w\in\Sigma^*$ ...
Coping Forever's user avatar
2 votes
1 answer
53 views

How to show that only this regular expression solves this equation

Consider the equation $x=v\cdot x + w$ where $x$ is a variable regular expression, $v, w$ are fixed regular expressions, $v$ has no variables inside it, and $w$ has no $x$ inside it. It is easy to ...
user837242's user avatar
0 votes
1 answer
55 views

Concatenation of languages - Basics

Just trying to understand a homework problem in my theory of computation class: $L_1 = (a^nb^n: n > 0)$ and $L_2 = (c^n: n > 0)$ List the concatenation of $L_1L_2$ where $n = 2$. I can find lots ...
AmandaF's user avatar
0 votes
1 answer
46 views

How to get words that belong to the language of this regular expression and four which do not, ((a|baa) ∗ (b|ab))∗ .

In the alphabet {a, b} for both automata and regular expressions, what would be four words that belong to the language of this regular expression and four which do not, regular expression = ((a|baa)∗(...
user avatar
-1 votes
1 answer
31 views

Prove a class of regular languages is not closed under a weird concatenation operation [closed]

Let's say we have an operation $L$ and a language $S$. $L(S) = \{s^n ~|~ s \in S, n \geq 0\}$. How can I prove a class of regular languages is not closed under this operation?
user1239142's user avatar
1 vote
1 answer
65 views

Is the Language $L = \{a^n b^m c^k d^q e^r \,|\, n, m, k, q, r \geq 0\}$ a Valid Regular Language?

I am inquiring about the nature of language L. It appears that L is not categorized as a regular language due to its unique characteristics, which involve the need to count occurrences of multiple ...
Tips's user avatar
  • 388
0 votes
0 answers
46 views

Regular Expression for the set of all binary strings that are of even length with at most 2 zeros

I asked the converse just recently. But now trying to understand this version.. I'm working with case work and then I will take the union of all three cases where its strings with no zeros, 1 zero, ...
Money Mit's user avatar
0 votes
1 answer
366 views

Regular Expression for the set of all binary strings that are of even length with at least 1 zero

Also followup question is the set of all binary strings that are of even length with at least two zeros. But for both questions I'm thinking of building my regular expression with casework, no zeroes, ...
Money Mit's user avatar
1 vote
1 answer
143 views

Let $L$ be a regular language. Prove that $L_1$, the language created by removing all characters in odd places in all words of $L$, is regular

Let $L$ be a regular language. Prove that $L_1$, the language created by removing all characters in odd places in all words of $L$, is regular. Completely stuck on this one. I tried building DFA,NFA,$...
Kantig Shoter's user avatar
2 votes
2 answers
75 views

Prove that if M is regular then sandwiched M is regular as well

Hi I'm having some confusion with regular languages and DFAs. Let's say we have some language M defined as $M = \{11, 1010\}$. Then let's define some $M[0]$ be defined formally as $\{x_10x_2...0x_n | ...
Money Mit's user avatar
0 votes
1 answer
43 views

Generating functions of ambiguous regular languages are still rational?

The Chomsky-Schützenberger theorem states that any context-free unambiguous language admits an algebraic generating function. For unambiguous regular languages, the generating function is always ...
Zhang Ruichong's user avatar
0 votes
1 answer
52 views

Is there a name for the set of single-character prefixes of words in a regular language

This question concerns regular languages and regular expressions. Suppose we have an alphabet $\Sigma$ and a language $\mathcal{L}$. For some algorithm, I am particularly concerned with the set of ...
AZWN's user avatar
  • 1
1 vote
1 answer
47 views

Computer Science: regular languages

Is it possible to prove with pumping lemma that the languge $$L=\{w_1w_2 \mid w_1,w_2\in\{a,b,c\}^* \text{ and } \#_a(w_1)>\#_b(w_1) \text{ and } \#_b(w_2)>\#_c(w_2)\}$$ (where $\#_x(w)$ is the ...
schegga_B's user avatar
0 votes
1 answer
58 views

Find all strings of $w$ that satisfy following equation

Solve the following string equation on the alphabet $A = \{1, 0\}$ and find all $w$'s: $w011 = 011w$
Sina Jani's user avatar
1 vote
0 answers
58 views

Can substrings of a regular language always be recognized by an "isolated" path in some finite state automaton?

I believe I have found a proof of the question I originally asked (see crossed out paragraph), but I have realized that what I actually need to prove is somewhat stronger. What I am actually wondering ...
M. Sperling's user avatar
2 votes
0 answers
73 views

Are $111^*$ and $11^*1$ equivalent?

I know it is a trivial question but are $111^*$ and $11^*1$ equivalent? (I think yes because I can have 11 in both at minimum but that seems odd to be true). I am trying to understand automata theory ...
bestgamer14's user avatar
0 votes
0 answers
53 views

Regular expression .Find it

Construct a regular expression that defines the language of all words that contain either the aa-substring or the bb-substring but NOT BOTH the aa-substring and the bb-substring in the same word....
Veekash Singh's user avatar
-2 votes
2 answers
111 views

Regular expressions creating language m

Construct a regular expression that defines the language M (say) containing all words beginning with exactly one a or exactly one b. (Words in M are at least of length 1 and words such as aa, bbbaba ...
Veekash Singh's user avatar
2 votes
1 answer
44 views

Find the mistakes(pumping lemma proof). Can you help me?

There are pumping lemma proof. I have to find one mistake. Please help me [lemma proof][1]
adelorean's user avatar
1 vote
0 answers
48 views

Let 𝐿 be a regular language. Prove all minimal automata for the language are isomorphic

I have started to study formal languages, especially finite automata and regular languages and I encountered some difficulties, i.e. Is this true: Automata will be called isomorphic if, by changing ...
NitaStack's user avatar
0 votes
0 answers
61 views

Proof that $L =$ {$a^p : \text{p is prime} $} is not regular

I know that this question has already been answered but the proofs provided do not seem intuitive to me and I propose one using Wilson's theorem. Say $L$ is regular and its pumping length is $p \geq ...
PatelisGM's user avatar
0 votes
0 answers
35 views

prove using Nerode law that a language is regular

prove that the language 𝐿 = {𝑤 ∈ Σ∗|∀1 ≤ 𝑖 ≤ 𝑛: #𝜎𝑖(𝑤) ≤ 𝑖 }, where 𝐿 is defined over Σ = {𝜎𝑖 | 1 ≤ 𝑖 ≤ 𝑛} is regular using Nerode law. basically the string w has, at most, 𝑖 occurrences ...
alex's user avatar
  • 1
2 votes
0 answers
70 views

Prove that L = {$w∈${a,b,c}$^*$|w contains "abc"} is regular with Nerode theorem?

How to prove that $L = \{w \in \{a,b,c\}^* \mid w \text{ contains } abc \}$ is regular using the Nerode theorem? Attempt If I show that there are a finite number of equivalence classes for this ...
NiStack's user avatar
  • 53
0 votes
1 answer
56 views

Prove or disprove that L = {$a^nb^m$ | $m ≠ 3n + 5$} is a regular

How can I prove or disprove that $L = \lbrace a^nb^m$ | $m ≠ 3n + 5 \rbrace$ is a regular language? Attempt Assume $L$ is regular, then its complement $L^\complement$ is also regular. $L^\complement ...
NiStack's user avatar
  • 53
0 votes
1 answer
83 views

Is the following language is regular, context free, and/or decidable?

Given a language determine if it is regular, context free, and/or decidable. No proof needed, but an explanation would be appreciated. A = {a^n b^(2n+6) | n >= 0} My first guess is no its ...
user1179819's user avatar
0 votes
1 answer
69 views

Is the algorithmic problem for regular languages decidable?

I have an algorithmic problem, where I need to build an algorithm and say if the problem is decidable. Here it is: Regular languages $L_1$, $L_2$, and $L_3$ are given by finite automata. Is the ...
Vladyslav Chobotok's user avatar
1 vote
1 answer
111 views

How can I determine the language from a DFA?

I was given three DFAs to solve. I understand the first one is a*. I think the second one would be b*(a+)*. I cannot figure out what the third one would be, it seems like there are too many different ...
Nixa's user avatar
  • 11
1 vote
1 answer
61 views

Prove equivalence of two regex using basic identities.

I'm trying to prove the following identity $$ (x+y)^* = (x^*y)^*x^* = x^*(yx^*)^* $$ Using the following 12 identities $L + M = M + L$ $(L + M) + N = L + (M + N)$ $(LM)N = L(MN)$ $\emptyset + L = L + ...
nothatcreative5's user avatar
1 vote
0 answers
96 views

Is Pumping lemma so useful? (Michael Sipser "Introduction to the Theory of Computation 3rd Edition")

I am reading "Introduction to the Theory of Computation 3rd Edition" by Michael Sipser. Pumping lemma is the following proposition: THEOREM 1.70 Pumping lemma If $A$ is a regular language, ...
tchappy ha's user avatar
  • 8,650
1 vote
1 answer
35 views

Infinite number of regular exressions for a given language

Took a Theory of Computation exam where one of the questions was : Is there an infinite amount of regular expressions for the language $L=\{aa,bb\}$ ? The proof requested was just an informal one. My ...
PatelisGM's user avatar
1 vote
0 answers
47 views

regular languages and suffixes

Let $\Sigma$ be a finite alphabet. For a language $L \subseteq\Sigma^*$ we define: $$Suff(L)= \left\{x\in\Sigma^*| \exists u \in \Sigma^*, u\cdot x \in L\right\}$$ Show an example of a language $L$ ...
BridonElden's user avatar
0 votes
1 answer
57 views

Build automata for words with both "bab" and "abb"

I have two finite automata, one for words containing "bab" and one for words with "abb." I wish to build automata that represent the multiplication of both (words with both "...
JobStack's user avatar
1 vote
1 answer
2k views

Using pumping lemma show that language $L = \{a^{n^2} | n≥ 0\}$ is not regular.

Using pumping lemma show that language $L = \{a^{n^2} | n≥ 0\}$ is not regular. Is this approach correct? Let's assume that $L$ is regular so then the pumping lemma applies. Let $w = a^{n^2} ∈ L$. We ...
RandomGuyOnMath's user avatar
1 vote
0 answers
49 views

The connection between regular languages and formal power series

Is there a characterization of the regular languages involving formal power series? I saw $\frac{1}{1-x} = 1+x+x^2+x^3+\cdots$ and $A^* = \epsilon + A + AA + AAA + \cdots$ in two different contexts on ...
TomKern's user avatar
  • 2,922
0 votes
0 answers
35 views

Myhill Nerode Theorem equivalence classes

Let L = {{a,b,c,d,e}* | each letter of alphabet appears exactly once in the word}. Prove that L has at most 40 and at least 10 equivalence classes. Also, find an estimate for general k. My approach: ...
Charlie's user avatar
  • 199
-2 votes
1 answer
62 views

Determining whether a given language is regular

Suppose language $L = \{\,a^{i} b^{k} : k \text{ divides } i\,\}$. Some strings in $L$ include … $\,a^{0} b^{1} = b \in L\,$ since $1 \text{ divides } 0$ $\,a^{1} b^{1} = ab \in L\,$ since $1 \text{ ...
user3134725's user avatar
1 vote
0 answers
51 views

Regular Expression Identities list?

I have been working on problems to simplify or equate certain regular expressions to others but so far the list of identities I have found in my textbook (Sipser) doesn’t tell me enough to simplify ...
Axo's user avatar
  • 279
1 vote
2 answers
611 views

Finding the set of strings over {𝑎,𝑏} that ends with an odd number of "a"s

I need to write a regular expression that identifies the set of all possible strings over Σ={𝑎,𝑏} that end with an odd number of "a"s. I'm getting better with regular expressions, but ...
CurlyError's user avatar
0 votes
0 answers
83 views

Regex groups and complements

Not sure about the "math" language of that but ill try to explain my question: Assume we have two regexes A, B. I say Regex ...
AD1234's user avatar
  • 1
-2 votes
1 answer
84 views

are two sets of infinity necessarily equal | Automata

we'll define the relation $\equiv_L$ (same one as the one in Myhill-Nerode theorem) as follows: there exists two string $x,y$ and a language $L$ under the $\Sigma$ alphabet $x\equiv_Ly$ if there $\...
user avatar
1 vote
1 answer
127 views

Proving a class of languages is closed under union when it closed under concatenation, (inverse) homomorphic images, and intersections.

Let $C$ be a class of languages closed under concatenation ($\cdot$), intersection, homomorphic images, inverse homomorphic images, and intersection with regular languages. Prove that $C$ is also ...
AspiringMat's user avatar
  • 2,428
0 votes
0 answers
48 views

What is the language generated by this grammar?

S → 0A | 1B | ɛ | 0 A → 0A | 0S | 1B B → 1B | 1 | 0 I've tried to find some specific properties of some of the generated words, but I've failed.
mdirfan's user avatar
  • 37
0 votes
0 answers
53 views

Proving Language is Non Regular With Pumping Lemma [duplicate]

I have the formal language $Z$ over the alphabet $Q \{a, b, c\}$ and it is generated by the context-free grammar whose non-terminals are $S, A$, and $B$, the start symbol is $S$, production rules are ...
Renee Ofadu's user avatar
-1 votes
2 answers
77 views

Proving Language is Non Regular Using Pumping Lemma

I am working on a question where I have the formal language Z over the alphabet Q {a, b, c} and it is generated by the context-free grammar whose non-terminals are S, A, and B, the start symbol is S, ...
Renee Ofadu's user avatar

1
2 3 4 5
25