# Questions tagged [regular-languages]

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

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

### Is Python a context-free language?

From Wikipedia: Off-side_rule#Implementation, there is a statement: ...This requires that the lexer hold state, namely the current indentation level, and thus can detect changes in indentation ...
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 ...
342 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 ...
3k views

7k views

### How do I find a regular expression for a particular language?

I have a language, and I want to find a regular expression for the language. How do I do that? Is there a step-by-step, systematic procedure for that? Pretend I am just learning this topic; what ...
448 views

### Possessive Kleene star operator

Has anyone studied the consequences of the Kleene star in regular expressions to always be "possessive"? In other words, if * would always match as much as ...
2k views

### Context-free language and regular expressions

I have the following context-free language: S -> ASa | b A -> aA | a I don't understand why this is not regular. I first said that it's generated by the ...
21k views

### Proving L = {${ a^{2^n} \ | \ n \ge 0 }$} 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. We have the language L = {${ a^{2^n} \ | \ n \ge 0 }$} ...
51 views

### Two languages such that $L_1 \cup L_2 \leq_m\, L_1 \cap L_2$ and two (other?) such that $L_1 \cap L_2 ≤_m\, L_1 \cup L_2$?

Are there languages $L_1$, $L_2$ such that such that $$L_1 \cup L_2\leq_m\, L_1\cap L_2,$$ and two other languages such that $$L_1 \cap L_2 \leq_m\, L_1 \cup L_2?$$ And if so, what are they? How ...
123 views

799 views

### Proving that if L is regular. Then L′ = {ww : w ∈ L} is regular

I believe this statement to be true. And here's my reasoning: Based on regular languages properties, the concatenation of two regular languages is regular. And since L′ = L · L, it follows that L′ ...
4k views

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 = \... 2answers 572 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 ... 1answer 191 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 ... 1answer 867 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$...
I was wondering if there is a polynomial time algorithm to test whether a DFA recognizes a star closed language ( which is if $A=A^*$). I think that yes, but I do not have an idea to do it.