The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
7
votes
1answer
105 views

Subsequence of one string but not of others

Let $\Sigma$ be an alphabet, and let $x^+,x^-_1,\dots,x^-_n \in \Sigma^*$ be strings over that alphabet. Call a string $s \in \Sigma^*$ good if $s$ is a subsequence of $x^+$ but not a subsequence of ...
7
votes
1answer
4k views

If $L$ is a regular language then so is $\sqrt{L}=\{w:ww\in L\}$

I am interested in proving that $\sqrt{L}=\{w:ww\in L\}$ is regular if $L$ is regular but I don't seem to be getting anywhere. If possible I was hoping for a hint to get me going in the right ...
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 ...
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 \...
6
votes
4answers
375 views

Why does $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ generate a context free language for regular $L$?

How can I prove that the language that the operator $A$ defines for regular language $L$ is a context free language. $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$, where $x^R$ is the ...
6
votes
2answers
1k views

Is there a reasonable and studied concept of reduction between regular languages?

Have been any interesting formulations for the concept of reduction between regular langauges, and if so -- are there regular-complete languages under those reductions?
6
votes
2answers
85 views

Can the regular image of a context-free language be undecidable?

I just need to know the truth or falsity of a simple statement. Let $L_1$ be a context-free language over an alphabet which contains some number of characters $\Sigma$, as well as a single, special ...
6
votes
1answer
233 views

regular expression given the language

The language is: $$ L = \{ (a^n) (b^m) \mid n + m = 3k, k \ge 0 \} $$ My attempt at an answer: $$ (a \cup b)^{3k} $$ This will work if the a OR b can change for each instance in the string that is (...
6
votes
2answers
2k views

Detecting palindromes in binary numbers using a finite state machine

In my first algorithms class we're creating these patterns that are supposed to model a finite state machine. We were given a task to think if we can figure out a way to detect palindromes in binary ...
6
votes
2answers
1k views

Space complexity below $\log\log$

Show that for $l(n) = \log \log n$, it holds that $\text{DSPACE}(o(l)) = \text{DSPACE}(O(1))$. It's well known fact in Space Complexity, but how to show it explicitly?
6
votes
2answers
550 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 ...
6
votes
1answer
186 views

Characterising $(aa)^*$ in first order logic

In my descriptive complexity class, we've been asked to find a formula that characterises the language $(aa)^*$ (over the alphabet $\{a\}$) with a first order formula over the language $\{<, P_a\}$....
6
votes
2answers
116 views

What is the field studying the search and generation of computer programs?

This Github repo hosts a very cool project where the creator is able to, give an integer sequence, predict the most likely next values by searching the smallest/simplest programs that output that ...
6
votes
3answers
115 views

For regular languages A and B, determine whether B might match early in (A B)

I have two regular languages A and B, and I want to determine whether there is any pair of strings, a in A and b in B, such that (a b) is a prefix of a string in (A B) and the left-most ...
6
votes
3answers
117 views

First half of context-free palindromes

If $L\subseteq\Sigma^*$ is a regular language, then $\text{mir}(L) = \{ww^R \mid w\in L\}$ is context-free. This is a nice exercise. Question: does the reverse hold? Thus, if $\text{mir}(L)$ is ...
6
votes
1answer
109 views

Determining a minimal-state regular language $A$ such that $A \cap B = C$ given regular languages $B$ and $C$

Suppose I have a regular language $B$ and a regular language $C$ such that $C \subseteq B$. How do I find a regular language $A$ such that $A \cap B = C$, where $A$ is represented by a DFA with as ...
6
votes
1answer
114 views

Regular sets have linear growth?

Is it true that the set $\{ 0^{n^2} \mid n \in\mathbb{N} \}$ is not regular because it does not grow linearly? Regular sets are called regular because if you have a regular set then you can always ...
6
votes
2answers
255 views

Infinite non-regular decompositions of regular languages

The title pretty much says it: I'm interested in examples of infinite families of non-regular, pairwise disjoint languages whose union is regular. When is this the case? Or, from a different ...
6
votes
1answer
171 views

A Myhill-Nerode type characterization of the regular languages using fooling sets?

Ultimately, my question is whether it's possible to exactly characterize the regular languages in terms of fooling sets. To help explain my motivation for asking this, here's a quick exposition. Let $...
6
votes
2answers
7k views

Cost in time of constructing and running an NFA vs DFA for a given regex

Repost from Stack Overflow: I'm going through past exams and keep coming across questions that I can't find an answer for in textbooks or on google, so any help would be much appreciated. The ...
6
votes
1answer
1k views

context free grammar to NFA

I've been given an exercise to solve which goes as follows: generate an NFA from the given CFG, $$\begin{align*}S &\to AB \mid c\\ A &\to aAb \mid c\\ B &\to bBa \mid c\ . \end{align*}$$ ...
5
votes
4answers
1k views

Without using pumping lemma, can we determine if $A =\{ww \mid w \in \{0,1\}^* \}$ is non regular?

Without using pumping lemma, can we prove $A =\{ww \mid w \in \{0,1\}^* \}$ is non regular? Is $L= \{w \mid w \in \{0,1\}^* \}$ non regular? I'm thinking of using concatenation to prove the former ...
5
votes
3answers
396 views

Is an irregular language concatenated with a language with which it has no common symbols irregular?

Here's an example of what I'm talking about. Suppose I have a languages $$ L_{1} = \{a^ib^i \mid i>0\},\\ L_{2} = \{c^i \mid i>0\} $$ and $$ L_{1}L_{2} = \{a^ib^ic^i \mid i>0\} $$ Is it ...
5
votes
3answers
2k views

Is it compulsory that every infinite set be non regular?

I am confused regarding the statements provided by one of our faculty regarding "Is it compulsory that every infinite set is non regular though every finite set is a regular set". Providing ...
5
votes
2answers
2k views

String of minimum length in $\{a, b\}^*$ not in a regular expression

I'm doing an exercise in my book, the question is to find a string of minimum length in $\{a, b\}^*$ not in the language corresponding to the given regular expression. a. $b^*(ab)^*a^*$ My answer: $...
5
votes
3answers
2k views

Intersection of Turing-recognizable language and regular language

True or false: An intersection of a Turing-recognizable and a regular language is always Turing-decidable. This was asked on a practice test and the answer is False. Why? I thought regular languages ...
5
votes
2answers
198 views

Why is this language involving reversal regular?

For a language to be regular it needs to be recognized by DFA/NFA. Let $L = \{ xy^rzyx^r \mid |x| , |y|, |z| \ge 1 \}$ over the alphabet $\{0,1\}$. $x^r$ means the reverse of $x$. A DFA has no ...
5
votes
3answers
276 views

Length of mid part of the string in Pumping Lemma

This standard definition of pumping lemma from Wikipedia. Let $L$ be a regular language. Then there exists an integer $p\ge 1$ (depending only on $L$) such that every string $w$ in $L$ of length ...
5
votes
2answers
216 views

Check the Regularity of the folowing Languages

Let $A$ be a regular set. Consider the two sets below. \begin{align*} L_1 &= \{ x \mid \exists{n}\geq 0 , \exists{y} \in A : y =x^{n} \}, \\ L_2 &= \{ x \mid \exists{n}\geq 0 , \exists{y} \in ...
5
votes
1answer
971 views

Is every language with a finite number of strings regular?

Is every language with a finite number of strings regular? Is the language of all strings regular? I am new to this topic and got confused. Can any one please help me with this?
5
votes
2answers
320 views

What's the reason for the second condition of the pumping lemma(s)?

For a language $L$ with pumping length $p$, and a string $s\in L$, the pumping lemmas are as follows: Regular version: If $|s| \geq p$, then $s$ can be written as $xyz$, satisfying the following ...
5
votes
1answer
278 views

Closure against the operator $A(L)=\{ww^Rw \mid w \in L \wedge |w| \lt 2007\}$

I would like your help with the following question: Let $L$ be a language, and operator $A(L)=\{\,ww^Rw \mid w \in L\ \wedge\ |w| \lt 2007\,\}$ where $x^R$ is the reversed string of $x$. Which of ...
5
votes
1answer
980 views

Chomsky normal form and regular languages

I'd love your help with the following question: Let $G$ be context free grammar in the Chomksy normal form with $k$ variables. Is the language $B = \{ w \in L(G) : |w| >2^k \}$ regular ? ...
5
votes
2answers
615 views

Undecidable Problem for Regular Languages

It might seems weird, but, Are there any undecidable problems concerning regular languages? I mean questions concerning the regular languages, not the problems like "Is the language of a TM regular?". ...
5
votes
2answers
299 views

Cyclic deterministic finite automata, exponential advantage over DFA

Let's define Cyclic deterministic finite automata (CDFA) as a DFA that treats its input a bit differently -- namely, CDFA when given input $w$, firstly transforms its input into $w@$, where $@$ is a ...
5
votes
2answers
872 views

Pumping lemma: if you can keep pumping, what does this tell you?

Hypothetically, let's say you are using the pumping lemma for either regular or context free languages. Now using either, you come across a case that remains true despite pumping it. In this situation,...
5
votes
1answer
2k views

Are HTML and CSS regular languages?

I have a question whether or not CSS and HTML are regular languages. I believe CSS is a regular language, since it should be possible to create a regular expression to match the structure of CSS. ...
5
votes
1answer
4k views

DFA for a strings whose every subsequence of length five has at least two zeroes

I have a regular language consisting of such {0,1}^k sequences, in which every subsequence of length 5 has at least two 0's in ...
5
votes
1answer
10k views

designing a DFA and the reverse of it

There is a theorem that says if a language is regular, it's reverse is regular as well. How can I draw a DFA that shows if a language is regular, it's regular as well?
5
votes
2answers
339 views

Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular

Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular. These are the things that I would use to start. As $L_1L_2$ is regular, then the homomorphism $h(L_1L_2)$ is regular. Let $h(L_1)...
5
votes
2answers
332 views

Constructive proof to show the quotient of two regular languages is regular

I have a question regarding the quotient of two regular languages, $R$ and $L$. I saw the answers to this question: are regular languages closed under division and the proof sketch is not ...
5
votes
2answers
252 views

How similar are two DFAs? -not just binary equivalence-

Are there any measures to compute similarity (or distance) between two DFAs? If yes, which are the main references? I need a measure of similarity, not only a (binary) equivalence test. "Similarity"...
5
votes
3answers
1k views

Why is the number of states for DFA is 3n + 1 for this language

I'm taking online compilers course. It's long ended, so it wouldn't be cheating to ask a question on quiz here. Let $S_i$ be the string consisting of $i$ 0's followed by $2i$ 1's. Define the language ...
5
votes
3answers
1k views

Is {wxw^r} a regular language?

Is $\{ WxW^{\mathrm{R}} \mid W,x\in\{0,1\}^+\}$ a regular language? If so, why? The notation $W^{\mathrm{R}}$ means the reverse string of $W$? If we consider the best answer in this solution, ...
5
votes
3answers
2k views

Proving a grammar only generates words whose alternating digit sums are multiples of three

This is homework and I'm looking for a push in the right direction. Proofs were never something I was properly taught, so now they're kind of a weak point. Here's the problem: The following ...
5
votes
1answer
6k views

Does a DFA accept an empty string if $q_0$ is the accept state?

Suppose $q_0$ is the start state, does this mean that if it's the accept state, then the machine must accept the empty string since it cannot have a transition with the empty string?
5
votes
2answers
65 views

Is relative regularity distinct from regularity?

Let $L$ and $G$ be languages over a finite alphabet $\Sigma$. $L$ is regular relative to $G$ if $L \subseteq G$ and there is a finite automaton that accepts every input in $L$, and rejects every input ...
5
votes
1answer
302 views

Why is $\{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ an inherently ambiguous language?

I came across a very hard interview question in last month’s Ph.D. entrance exam. It was asking which one of the languages is inherently ambiguous. Short answer says 2). Why is the language in 2) an ...
5
votes
4answers
2k views

Proof that regular languages are closed against taking the even-length subset

This question is on the GRE Computer Science test booklet (not homework). I tried applying closure properties of regular languages but no success. Suppose $L$ is a regular language over $\Sigma = \{0,...
5
votes
1answer
2k views

Prove that the language of non-prime numbers written in unary is not regular

Im trying to prove that the following language is not regular. $$\text{Notprime} = \{a^n \text{where \(n\) isn't prime}\} = \{\epsilon, a, aaaa, aaaaaa, aaaaaaaa, \ldots\}$$ Heres what I have: "If ...