Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
4
votes
3answers
3k views

Show that regular languages are closed under Mix operations

Let $L_1, L_2$, two regular languages and the operations: $$Mix_1(L_1, L_2) =\{ a_1b_1a_2b_2\ldots a_nb_n | n\ge 0 \land a_1,a_2,\ldots ,a_n,b_1,b_2,\ldots ,b_n\in\Sigma\\ \land a_1a_2\ldots a_n\in ...
4
votes
1answer
5k views

Do self-loops in DFA cause infinite languages?

A true/false question: If a DFA $M$ contains a self-loop on some state $q$, then $M$ must accept an infinite language. The answer is "false". I've read this question, but I'm still wondering why $M$ ...
4
votes
2answers
3k views

Infinite Intersection/Union of regular languages

Hello I'm having trouble understanding how an intersection/union of regular languages can be regular and in other case non-regular. Can someone please give me some good examples?
4
votes
3answers
155 views

Was there an attempt to make reusable regular expressions?

In everyday practice I often encounter tasks which would benefit from being able to define aliases for chunks of regular expressions to reuse them later. Typical examples include: parsing a floating ...
4
votes
2answers
2k views

Determine if this language is regular

Let $L = \{xyx \mid \text{ for some }x,y \in \{0,1\}^+\}$. Is this language regular? So I was trying to construct a DFA, but I don't how to do this with this language.
4
votes
3answers
5k views

Is the language that accepts strings concatenated with their reverse regular?

If the set of regular languages is closed under the concatenation operation and is also closed under the reverse operation ($x^R$ is the reverse of $x$) then is the language generated by $$\{ww^R|w\in\...
4
votes
3answers
191 views

Language of the graph of an affine function

Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let : be a symbol distinct from any digit. Let $a$ and $b$ ...
4
votes
2answers
102 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 ...
4
votes
1answer
199 views

Show $L = $ { w $\in (a,b) ^* $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$ is regular

I try to show that this language is regular: $L = $ { w $\in \ (a,b) ^ * $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$ If I build a NFA and run on it every substring of w (skip other letters ...
4
votes
2answers
87 views

Proving that $\{0^{m^2}\mid m\geq 3\}^*$ is regular

We know that $L=\{0^{m^2}\mid m\geq 3 \}$ is not a regular language. However $L^*$ is regular because we can generate $0^{120}$ to $0^{128}$ by some concatenations and then any other power of $0$ can ...
4
votes
1answer
331 views

How does a regular language satisfies the second condition of the pumping lemma

I'm a little bit confused about the second condition of the pumping lemma which are: $|y|\geq1$ $|xy|\leq p$ $\forall i \geq 0 : x y^i z \in L$ I don't understand why the length of substrings $xy$ ...
4
votes
1answer
146 views

What does $\{$ a set $\}^{+}$ mean in the context of languages?

I came across this notation and I don't know the meaning of it, or if it's a typo: $\{$ some set $\}^{+}$ What does the + mean, i.e., the plus operator applied to a set?
4
votes
2answers
2k views

Do Kleene star and complement commute?

I am having hard time solving the following problem. Are there any languages for which $$ \overline{L^*} = (\overline{L})^* $$ Assuming $\emptyset^* = \emptyset$, if I consider $\Sigma = \{a\}$ ...
4
votes
1answer
13k views

Is every regular language Turing-decidable, and how can we prove this?

I know every regular language is Turing-acceptable, but does that imply it is Turing-decidable?
4
votes
2answers
70 views

Formal Language Syntax

Here is the question: Show that $L = \{0^m1^n : m > 1, n > 1, n < m \}$ is not regular. I am not sure what superscripts mean in this situation? Does it mean something like this: $0^5 = ...
4
votes
1answer
271 views

Pumping Lemma: is it valid to "multiply the product of powers" in this case?

I need to show that $\qquad \displaystyle S = \{(10^p)^m \mid p \geq 0, m \geq 0\}$ is not a regular language using pumping lemma. Can I multiply the product of the powers and express it to: $S = \...
4
votes
2answers
914 views

Does closure under union and concatenation imply closure under Kleene star? [duplicate]

For decidable languages (or a particular subset of decidable languages, e.g., regular, context free) does closure under Kleene star follow from the proof of closure under union and concatenation? The ...
4
votes
1answer
357 views

When does the product automaton of two NFAs A and B not decide L(A) U L(B)?

We are given the following task: Let $\mathcal{A} = {}(Q_A,\Sigma, \delta_A, s_A, F_A)$ and $\mathcal{B} = {}(Q_B,\Sigma, \delta_B, s_B, F_B)$ be two NFAs and let their product automaton be defined ...
4
votes
1answer
1k views

Non-regularity of the set of primes in unary encoding using Myhill-Nerode

I have found many proofs for this using pumping lemma, I'm curious of how to proof it via Myhill-Nerode theorem. Suppose $L= \{a^p \mid p \text{ is prime}\}$ is regular. Then we have congruence such $...
4
votes
2answers
1k views

How to prove "if every subset of a set is a CFL, then the set must be regular."

"If every subset of a set is a CFL, then the set must be regular." I want to prove it, could anyone please give me some hints?
4
votes
1answer
2k views

Why does this pumping lemma application "prove" that 0*1* is not regular?

Here is a proof that $0^*1^*$ is not regular, even though it is regular. I'm having a hard time figuring out what is wrong with the proof. Assume $0^*1^*$ is regular. Let $p$ be the pumping length as ...
4
votes
2answers
893 views

Regular expressions and semi-linear sets

In proving Parikh's Theorem, my Theory of Computer Science textbook defines a linear set as: $u_0 + \langle u_1, \dots, u_m \rangle = \{u_0 + a_1u_1 + \dots + a_mu_m \mid a_1, \dots, a_m \in \mathbb{...
4
votes
1answer
163 views

Are these two languages regular?

Let $\operatorname{value}(x)$ be the result when the symbols of $x$ are multiplied from left to right according to $\qquad \displaystyle\begin{array}{c|ccc} \times & a & b & c \\ ...
4
votes
2answers
73 views

Does there exist a context-free language $L$ such that $L\cap L^2$ is not context-free?

I can see that $L$ has to be context-free but not regular here as regular languages are closed under concatenation and intersection. But $L\cap L^2$ looks too weird. I couldn't think of any $L$ that ...
4
votes
1answer
10k views

Show that a language consisting of strings of a prime number of 1s is irregular using pumping lemma [duplicate]

Question: L is a language defined as $\ L = \{1^l | l\in primes\}$ (strings of 1s having a prime length). Show that this is not a regular language ($\ L \notin REG$). You may either use the theory ...
4
votes
1answer
200 views

Inverse Homomorphisms and Kleene star

The exercise is to prove or give a counterexample to the following proposition with $L \subseteq \Gamma^*$ regular and $h: \Gamma \to \Sigma^*$ a homomorphism. Is there any regular language $L'$ such ...
4
votes
1answer
2k views

Proving that the scramble of a regular language is context-free

For strings $w$ and $t$, if they have the same length and comprise the same characters (namely, they are two permutations of these characters), then $w\sim t$. For a string $w$, define an operator $\...
4
votes
1answer
3k views

Given regular expression construct regex for the complement language

Disclamer: this is my uni assignment, which is rated comparatively low, thus I assume that the answer should be simple. Hints are appreciated (as opposed to direct answers). Write an algorithm ...
4
votes
1answer
3k views

What does the R superscript notation mean in regular/formal languages?

What does the capital R superscript notation mean in regular languages? I am working on a homework assignment and don't recall my professor mentioning what the what the R superscript means. For ...
4
votes
2answers
170 views

Does O(1) communication complexity imply that a language is regular?

Let's say that we have a function $g(i,j)$, which is an arbitrary boolean-valued function over $i,j \in \{a,b\}^*$, such that $|i| = |j| = m.$ Moreover, we can also say that $g$ has communication ...
4
votes
1answer
271 views

How to prove the set of powers of 2 in ternary representation to be non-regular using pumping lemma?

Given the set of natural numbers, $S = \{2^i|i\in\mathbb{N}\}$ let $L$ be the language defined as the ternary representation of all numbers in $S$. How can you prove that this is not a regular ...
4
votes
1answer
698 views

Irregularity of language of prefixes of decimal expansion of pi

Let $L_{\pi}$ be the language consisting of prefixes of the decimal expansion of $\pi$: $$L_\pi = \{3, 31, 314, 3141, 31415, 314159, \ldots\}.$$ Prove that Lπ is not DFA-recognizable. You may use the ...
4
votes
1answer
125 views

The equational theory of regular languages has no finite set of axioms for general alphabets

According to Redko the equational theory of regular languages with operations $+, \cdot, *$ over a single letter has no finite set of axioms. Why does this imply that it has no finite set of ...
4
votes
1answer
1k views

Using finite state machines for lexical analysis

I'm a high school student and I'm passionate about everything language related - lexers, parsers, compilers, interpreters and so on. Some time ago I've written a calculator in Python (now willing to ...
4
votes
1answer
2k views

Practical Applications of regular grammars

A regular grammar is a mathematical object, $G$, with four components, $G = (N, Σ, P, S)$, where. $N$ is a nonempty, finite set of nonterminal symbols, $Σ$ is a finite set of terminal symbols , or ...
4
votes
1answer
274 views

Show that some context free languages must contain more that one non-terminal

Context free languages that has only one non-terminal is a proper subset of context free languages and they does not contains regular set. Since, CFL is more powerful than FSM and contains regular set,...
4
votes
4answers
9k views

Why is $L= \{ 0^n 1^n | n \geq 1 \}$ not regular language?

I'm looking for intuition about when a language is regular and when it is not. For example, consider: $$ L = \{ 0^n 1^n \mid n \geq 1 \} = \{ 01, 0011, 000111, \ldots \}$$ which is not a regular ...
4
votes
1answer
59 views

$\{uuv\mid u\in\Sigma^+, v\in \Sigma^*\}$ and pumping lemma

As I am currently teaching regular languages and pumping lemma, I was searching for nice examples of languages, regular or not, for exercises. $L_1 = \{vv\mid v\in \Sigma^*\}$ is a classic example, ...
4
votes
2answers
75 views

Is the language "substrings of a regular language that are over half the length of the superstring" regular?

We say $x$ is a majority substring of $y$ if $y \in \Sigma^* x \Sigma^*$ and $|x| \geq \frac 12|y|$. If $B$ is a regular language, is the set of majority substrings of $B$ regular? I was provided the ...
4
votes
1answer
56 views

Does the following operation makes the language regular? [duplicate]

I came across a question stated as $L = \{wxwy \mid w \in \{0,1\}^* , x,y \in\{ 0,1\}^* \}$ is regular and I have no problem understanding it. However I thought what could happen if the language is ...
4
votes
1answer
809 views

Pumping Lemma for single character language [duplicate]

I have a question about the Pumping lemma. Condition $2$ of the pumping lemma for a string division $xyz$ states that the middle portion of the string $y^i$ can be 'pumped' for any $i$ greater than or ...
4
votes
1answer
77 views

Is repetition the origin of countability?

The original question was "Do all non-regular languages have an uncountable number of strings?". How can someone prove that..? I am squeezing my head but I can't figure it out. And the other side ...
4
votes
2answers
1k views

Is DFA a Moore machine or not?

I understand the difference between DFA (has finite set of accept states, and doesn't have output function, nor output alphabet) and Moore Machine (doesn't have accept states, but has output for every ...
4
votes
1answer
1k views

Recursive definition of a language given the regular expression

Consider the language: $$ L_1 = \{ x \in \Sigma^* : x \text{ does not contain the substring } 110\} $$ I know that there is a DFA that accepts this language, and furthermore, that the regular ...
4
votes
1answer
714 views

Is the symmetric difference of a non regular language L and a finite language f non regular?

The symmetric difference of $L_1$ and $L_2$ is defined to be: $(L_1-L_2) \cup (L_2-L_1)$. Problem: I’m trying to prove that given L a non regular language and F a finite language there symmetric ...
4
votes
1answer
863 views

Do basic operators of RE (Union, Kleene star and Concatenation) have properties like associativity, commutativity, distrbutivity etc.?

So in regular algebra we have some basic operations defined such as multiplication, addition, subtraction and division. For these operations/operators, we have some properties like commutativity, ...
4
votes
1answer
490 views

How do I show that an equivalence class of a language containing an empty string is infinite

The question is as follows: Let $L$ be a language (not necessarily regular) over an alphabet. Show that if the equivalence class containing the empty string $[ \epsilon ]$ is not $\{ \epsilon \...
4
votes
1answer
755 views

Basic Myhill-Nerode Theorem Practice

I wanted to understand the Myhill-Nerode Theorem so I made up a small example to do so. L = (a $+$ b ) Clearly, this language is regular. So, I should be able to establish a finite number of ...
4
votes
1answer
210 views

Finding two words of lengths that are relatively prime in a regular language?

Given a regular language $L$ over a unary alphabet $\Sigma = \{ a \}$. How to decide whether there are two words $w,w' \in L$ such that the length of $w$ is relatively prime to the length of $w'$ ?
4
votes
1answer
73 views

Is unification over regular expression equations doable?

By way of example, suppose I know that $X + a = b + Y$ where $X$ and $Y$ are variables standing for regular expressions, then $(X, Y) = (b, a)$ is a solution to this set of equations. Generalizing ...

1
3 4
5
6 7
33