Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
75
votes
10answers
103k views

How to prove that a language is not regular?

We learned about the class of regular languages $\mathrm{REG}$. It is characterised by any one concept among regular expressions, finite automata and left-linear grammars, so it is easy to show that a ...
47
votes
8answers
68k views

How to prove a language is regular?

There are many methods to prove that a language is not regular, but what do I need to do to prove that some language is regular? For instance, if I am given that $L$ is regular, how can I prove that ...
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 ...
14
votes
3answers
1k views

What are the possible sets of word lengths in a regular language?

Given a language $L$, define the length set of $L$ as the set of lengths of words in $L$: $$\mathrm{LS}(L) = \{|u| \mid u \in L \}$$ Which sets of integers can be the length set of a regular language?...
11
votes
2answers
5k views

Single-tape Turing Machines with write-protected input recognize only Regular Languages

Here is the problem: Prove that single-tape Turing Machines that cannot write on the portion of the tape containing the input string recognize only regular languages. My idea is to prove that this ...
12
votes
7answers
1k views

Is $A$ regular if $A^{2}$ is regular?

If $A^2$ is regular, does it follow that $A$ is regular? My attempt on a proof: Yes, for contradiction assume that $A$ is not regular. Then $A^2 = A \cdot A$. Since concatenation of two non-...
13
votes
2answers
1k views

Closure against right quotient with a fixed language

I'd really love your help with the following: For any fixed $L_2$ I need to decide whether there is closure under the following operators: $A_r(L)=\{x \mid \exists y \in L_2 : xy \in L\}$ $A_l(L)=\{...
10
votes
5answers
1k views

Language of the values of an affine function

Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let $a$ and $b$ be integers, with $a > 0$. Consider the language of the decimal expansions ...
15
votes
1answer
20k views

Intersection of context free with regular languages

The intersection of a context free language L with a regular language M, is said to be always context free. I understood the cross product construction proof, but I still don't get why it is context ...
5
votes
2answers
827 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
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, ...
7
votes
1answer
847 views

What's wrong with my pumping lemma proof?

The language $L = \{0^{2n} \space |\space n \ge 0 \}$ is obviously regular – for example, it matches the regular expression $(00)^*$. But the following pumping lemma argument seems to show it's ...
17
votes
4answers
52k views

How to show that a “reversed” regular language is regular

I'm stuck on the following question: "Regular languages are precisely those accepted by finite automata. Given this fact, show that if the language $L$ is accepted by some finite automaton, then $L^{...
3
votes
5answers
40k views

Regular expression for the strings without a particular substring

How can we design a regular expressions without particular substrings. The goal of this is to create language L which won't contain a particular substring (i.e. 110)...
8
votes
1answer
735 views

Proving that language is regular or not regular

Let $L$ be a regular language. Prove that: $L_{+--}=\left\{w: \exists_u |u|=2|w| \wedge wu\in L\right\}$ $L_{++-}=\left\{w: \exists_u 2|u|=|w| \wedge wu\in L \right\}$ $L_{-+-}=\left\{w:\...
3
votes
3answers
2k views

Show that regular languages are closed under Mix operations

Let $L_1, L_2$, two regular languages and the operations: $$Mix_1(L_1, L_2) =\{ a_1b_1a_2b_2\ldots a_nb_n | n\ge 0 \land a_1,a_2,\ldots ,a_n,b_1,b_2,\ldots ,b_n\in\Sigma\\ \land a_1a_2\ldots a_n\in ...
19
votes
3answers
7k views

Pumping lemma for simple finite regular languages

Wikipedia has the following definition of the pumping lemma for regular langauges... Let $L$ be a regular language. Then there exists an integer $p$ ≥ 1 depending only on $L$ such that every ...
16
votes
3answers
6k views

Is there any uncountable Turing decidable language?

There are many(and I mean many) countable languages which are Turing-decidable. Can any uncountable language be Turing decidable?
7
votes
1answer
3k 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 ...
8
votes
1answer
6k views

Prove that regular languages are closed under the cycle operator

I've got in a few days an exam and have problems to solve this task. Let $L$ be a regular language over the alphabet $\Sigma$. We have the operation $\operatorname{cycle}(L) = \{ xy \mid x,y\in \...
15
votes
2answers
1k views

Number of words of a given length in a regular language

Is there an algebraic characterization of the number of words of a given length in a regular language? Wikipedia states a result somewhat imprecisely: For any regular language $L$ there exist ...
11
votes
1answer
1k views

Algorithm to test whether a language is regular

Is there an algorithm/systematic procedure to test whether a language is regular? In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n : n \in \mathbb{N}\...
9
votes
2answers
1k views

Smallest DFA that accepts given strings and rejects other given strings

Given two sets $A,B$ of strings over alphabet $\Sigma$, can we compute the smallest deterministic finite-state automaton (DFA) $M$ such that $A \subseteq L(M)$ and $L(M) \subseteq \Sigma^*\setminus B$?...
5
votes
1answer
3k 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 ...
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.
2
votes
1answer
2k views

are regular languages closed under division

I am trying to solve this question which appeared in previous exam paper Can someone help me what i am failing to understand For languages $A$ and $B$ define $A \div B = \{x \in \Sigma^{\ast} : xy ...
1
vote
1answer
420 views

Why the language of unary primes isn't regular

I have some difficulties proving that the language of unary primes ($L=\{1^p\mid p\text{ is prime}\}$) is not regular using the pumping lemma. Any suggestions?
8
votes
3answers
4k views

Deriving the regular expression for C-style /**/ comments

I'm working on a parser for a C-style language, and for that parser I need the regular expression that matches C-style /**/ comments. Now, I've found this expression on the web: ...
3
votes
1answer
1k views

Is $L_{half} = \{w : \text{for some } z \in L, x \in \Sigma^*, z = wx \wedge |w| = |x| \} $ regular? [duplicate]

Suppose we have some regular language $L$, then can we say that $$L_{half} = \{w : \text{for some } z \in L, x \in \Sigma^*, z = wx \wedge |w| = |x| \} $$ is also regular? I have a 'feeling' that ...
0
votes
1answer
664 views

Regular expression of a language over {a,b,c} which does not contain substring bbb

I'm trying to figure out how to build a regular expression for a language that doesn't contain substring bbb. The alphabet is {a,b,c}. I'm trying to construct a DFA and convert to help me get the ...
31
votes
5answers
5k views

Can regular languages be Turing complete?

I was reading about Iota and Jot and found this section confusing: Unlike Iota, where the syntactic tree for a string can branch either on the left or on the right, Jot syntax is uniformly left-...
12
votes
2answers
9k views

Are all context-free and regular languages efficiently decidable?

I came across this figure which shows that context-free and regular languages are (proper) subsets of efficient problems (supposedly $\mathrm{P}$). I perfectly understand that efficient problems are a ...
16
votes
2answers
3k views

Are regular expressions $LR(k)$?

If I have a Type 3 Grammar, it can be represented on a pushdown automaton (without doing any operation on the stack) so I can represent regular expressions by using context free languages. But can I ...
8
votes
3answers
2k views

Why isn't it simple to count the number of words in a regular language?

Given a DFA, A, let L(A) denote the number of words A accepts. I think it's easy to calculate L(A): Translate the encoding of A into a regular expression. If the Kleene star appears anywhere in the ...
7
votes
1answer
815 views

Time Complexity of Regular Languages

I wonder how I can go about proving that if a language L is decidable in o(nlog(n)) then L must be regular. I should probably mention that by "decidable" I mean "being decidable by single-tape ...
8
votes
1answer
1k views

Kleene star of an infinite unary language always yields a regular language

Let $L = \{a^n \mid n \ge 0\}$, where $a^0 = \epsilon$ and $a^n = a^{n-1}a$ for all $n \ge 1$. Thus $L$ consists of sequences of $a$ of all lengths, including a sequence of length $0$. Let $L_2$ be ...
13
votes
2answers
1k views

Is the language of words containing equal number of 001 and 100 regular?

I was wondering when languages which contained the same number of instances of two substrings would be regular. I know that the language containing equal number of 1s and 0s is not regular, but is a ...
12
votes
2answers
2k views

If $L$ is a subset of $\{0\}^*$, then how can we show that $L^*$ is regular?

Say, $L \subseteq \{0\}^*$. Then how can we prove that $L^*$ is regular? If $L$ is regular, then of course $L^*$ is also regular. If $L$ is finite, then it is regular and again $L^*$ is regular. Also ...
8
votes
5answers
1k views

Is there a known method for constructing a grammar given a finite set of finite strings?

From my reading it seems that most grammars are concerned with generating an infinite number of strings. What if you worked the other way around? If given n strings of m length, it should be possible ...
5
votes
2answers
310 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
212 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 ...
4
votes
2answers
3k views

Proving that any CF language over a 1 letter alphabet is regular

I would like to prove that any context free language over a 1 letter alphabet is regular. I understand there is Parikh's theorem but I want to prove this using the work I have done so far: Let L be a ...
3
votes
4answers
16k views

Designing a DFA that accepts strings such that nth character from last satisfies condition

This is a homework question, so I am only looking for hints. I got a question in an assignment which states : Design a DFA that accepts strings having 1 as the 4th character from the end, on the ...
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 ...
3
votes
3answers
3k views

If L is regular, show that even(L) is also regular

I am stuck on the following question. If $L$ is regular show that $\mathrm{even}(L)$ is also regular, where $\mathrm{even}(L) = \{ even(w) : w \in L \}$, $w$ is a string in $L$ and $\mathrm{even}(w)...
16
votes
2answers
2k views

Decidablity of Languages of Grammars and Automata

Note this is a question related to study in a CS course at a university, it is NOT homework and can be found here under Fall 2011 exam2. Here are the two questions I'm looking at from a past exam. ...
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 \...
3
votes
1answer
343 views

Closure of regular languages to shuffle using closure operations

Given a language: $L = \{\; a_1b_1a_2b_2a_3b_3\dots a_nb_n \mid \forall i: a_i,b_i \in \Sigma, a_1\dots a_n \in L_1\ , b_1\dots b_n \in L_2 \;\}$ Also $L_1, L_2$ are regular languages. Using ...
3
votes
2answers
533 views

Why is every finite language A ⊆ Σ* regular

So I've been doing regular languages a while and still need a better understanding of why all finite languages A ⊆ Σ* are regular? Is there a formal proof of it or is it just because a DFA can ...
2
votes
3answers
326 views

Regularity of “middles” of words from regular language

I need some help with the following problem. Let $L \subseteq \Sigma^*$ be a regular language. I have to prove that the language $P = \{\alpha \mid \beta\alpha\gamma \in L, \beta,\gamma \in \Sigma^*\}$...