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.

1,201 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
2k views

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 ...
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*} ...
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 ...
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 ...
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 ...
2k views

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 ...
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"...
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 ...
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, ...
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 ...
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?
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 ...
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 ...
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,...
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 ...