Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
5
votes
1answer
66 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
196 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
213 views

Closure of regular languages are closed under certain cut operations

Let $f : \mathbb{N} \to \mathbb{N}$ be an integer function. For a language $L$, define $$f(L) = \{w \mid \exists x : |x| = f(|w|) \text{ and } wx \in L\}$$ For example, if $f(n) = n$ this is just ...
5
votes
1answer
15k 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
164 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
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
1answer
47 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
118 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
2answers
6k 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
1answer
948 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
267 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
467 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
209 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
802 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
441 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
286 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
723 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
333 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
618 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
298 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
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
4k 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
826 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
139 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
183 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
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
2answers
81 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
128 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
65 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
218 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
458 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
144 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
713 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.
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
663 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
156 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
68 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
142 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
269 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
91 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

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
124 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
2answers
19k 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 } $} ...
4
votes
1answer
54 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
199 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 ...
4
votes
1answer
666 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 ...