Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
5
votes
3answers
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, ...
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
2answers
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 ...
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
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 ...
5
votes
4answers
3k 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 ...
5
votes
1answer
127 views

What can be said in general about a homomorphism between two regular languages?

In other words: is a homomorphism always guaranteed to exist between two arbitrary regular languages? If not (which I suspect), are there only a finite number of classes of languages, for which we can ...
5
votes
2answers
507 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?
5
votes
1answer
70 views

Formal languages: constructing * for a linear set

Right now, I'm working on a computer verified proof in Agda, showing that the Parikh images of regular languages are semi-linear (i.e. a limited form of Parikh's Theorem). Right now, I'm trying to ...
5
votes
1answer
199 views

Nondeterministic finite state machine without any initial state possible

Is it theoretically possible to have a nondeterministic finite state machine without any initial state or does it need at least one initial state?
5
votes
1answer
314 views

Efficiently convert an NFA with multiple $\varepsilon$ edges and accepting states into a regular expression

Given an NFA with alphabet $\Sigma = \{a, b, c\}$ defined in the diagram, is there a way to efficiently convert it into a regular expression? The way I solved this problem is to first convert the NFA ...
5
votes
1answer
18k views

Steps to convert regular expressions directly to regular grammars and vice versa

I came across following intuitive rules to convert basic/minimal regular expressions directly to regular grammar (RLG for Right Linear Grammars, LLG for Left Linear Grammars): Then I came across many ...
5
votes
1answer
179 views

Direct conversion from regular expression to MSO

A language $L \subseteq \Sigma^*$ can be described by a regular expression iff it can be defined by a formula in monadic second order with words as structure $(\{0, \dots, n-1\}, <, (P_a)_{a \in \...
5
votes
2answers
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 ...
5
votes
2answers
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 ...
5
votes
2answers
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 ...
5
votes
2answers
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 } $} ...
5
votes
1answer
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 ...
5
votes
1answer
123 views

Algorithm to find a minimal regular language containing given context-free language

I am not sure that the problem is in general solvable, but here's an example of what I mean: Any context-free language has a trivial regular language that contains it: $\Sigma^*$. The language $L_1=\{...
5
votes
1answer
1k views

Synchronizing sequence and Synchronizable DFA

I am trying to prove problem 1.59 in Sipser's book: Introduction to the theory of computation , 2nd Edition. Let $M=(Q,\Sigma,\delta,q_0,A)$ be a DFA and let $q'$ be a state of $M$ called its "home"...
5
votes
1answer
277 views

Undergrad resources for identifying regular languages with Myhill-Nerode matrices

I am taking an undergraduate CS Theory course and the material on finite automata and regular languages is being taught in a non-traditional manner. Instead of using regular expressions, the closure ...
5
votes
1answer
537 views

DFA, lower bound on number of states, language with primes and remainders

This is an exercise from old exam on formal languages that I don't know how to solve: Let $p \ge 5$ be a prime number and $L_p$ be a language of words over $\{0,1\}$ that read in binary from right (i....
5
votes
0answers
211 views

How to disambiguate symbolic regular expressions

What I mean by a "symbolic regular expression" (if there already is a different name for this I'm not aware of it) is a regular expression that may include exponents that are symbolic arithmetic ...
4
votes
2answers
870 views

How can the intersection of CFLs and REGs be CFL if REG is a proper subset of CFL?

Intersection of CFL and regular is always CFL. But according to Chomsky hierarchy diagram, regular languages lie completely inside CFL. So, as regular set is completely inside CFL set, their ...
4
votes
3answers
447 views

Proving a specific language is regular

In my computability class we were given a practice final to go over and I'm really struggling with one of the questions on it. Prove the following statement: If $L_1$ is a regular language, ...
4
votes
2answers
291 views

Find non-regular $L$ such that $L \cup L^R$ is regular?

I've been studying for an exam I have tomorrow, and I was looking through some previous sample exam questions, when I came across this problem: Give a non-regular language $L$ such that $L \cup L^R$...
4
votes
2answers
781 views

$L(M) = L$ where $M$ is a $TM$ that moves only to the right side so $L$ is regular

Suppose that $L(M) = L$ where $M$ is a $TM$ that moves only to the right side. I need to Show that $L$ is regular. I'd relly like some help, I tried to think of any way to prove it but I didn't ...
4
votes
2answers
317 views

Is this language regular or not?

$L_1=\{a^ku \mid u \in \{a,b\}^* $ and $u$ contains at least $k$ a's, for $k\geq 1\}$. If it is regular, I haven't found its regular expression or any closure property to prove it. If not, it seems ...
4
votes
2answers
336 views

DFA with limited states

Lets $L_z \ := \{ a^i b^i c^i : 0 \leq i < z \}$ $\{a,b,c\} \in \sum^*$ there is a DFA with $\frac{z(z+1)}{2}+1$ states - How can I prove this? And I need largest possible number $n_z$, for ...
4
votes
3answers
5k views

Irregularity of $\{a^ib^jc^k \mid \text{if } i=1 \text{ then } j=k \}$

I read on the site on how to use the pumping lemma but still I don't what is wrong with way I'm using it for proving that the following language is not a regular language: $L = \{a^ib^jc^k \mid \text{...
4
votes
1answer
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′ ...
4
votes
2answers
4k views

Why is this example a regular language?

Consider this example (taken from this document: Showing that language is not regular): $$L = \{1^n \mid n\text{ is even}\} $$ According to the Pumping Lemma, a language $L$ is regular if : $y \ne ...
4
votes
3answers
6k views

Write a regular expression - Contains an equal number of 01 and 10 subtrings

I'm trying to write a regular expression for the language $L\subseteq\{0,1\}^*$ of strings that begin with $0$ and contain an equal number of occurrences of the substrings $01$ and $10$. ...
4
votes
2answers
828 views

Difference between 1* + 0* and (1 + 0)*

I know that (1 + 0)* is the set of all bit strings; but isn't 1* + 0* the same thing?
4
votes
1answer
4k 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
3answers
140 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
4k 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
184 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
82 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
132 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
1answer
9k 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
66 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
235 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
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 ...
4
votes
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 ...
4
votes
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 $...
4
votes
1answer
1k views

Can we check in polynomial time if the language of a DFA is closed against Kleene star?

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.

1 2 3 4 5 26