Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [regular-languages]

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

2
votes
2answers
494 views

Counting with constant space bounded TMs

The problem, coming from an interview question, is: You have a stream of incoming numbers in range 0 to 60000 and you have a function which will take a number from that range and return the ...
10
votes
1answer
427 views

Are regular languages closed under sort (Parikh image)?

Assume $L$ is a regular language over an ordered alphabet. Is the language built by taking every word in $L$ and sorting it always a regular language?
0
votes
1answer
458 views

Does this regular expression equal this automata?

I just came across an exercise which is to find a regular expression for the following automata, such that the regular expression and the automata generate the same language. One solution presents ...
15
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 ...
6
votes
1answer
230 views

regular expression given the language

The language is: $$ L = \{ (a^n) (b^m) \mid n + m = 3k, k \ge 0 \} $$ My attempt at an answer: $$ (a \cup b)^{3k} $$ This will work if the a OR b can change for each instance in the string that is (...
1
vote
1answer
431 views

A regular expression for a given formal language

I wanted to ask if someone can help me to construct a regular expression over the alphabet $\{a,b,x\}$ for the language $L$ which is constituted by all strings containing an odd number of $a$'s, and ...
12
votes
2answers
8k views

Intersection and union of a regular and a non-regular language

Let $L_1$ be regular, $L_1 \cap L_2$ regular, $L_2$ not regular. Show that $L_1 \cup L_2$ is not regular or give a counterexample. I tried this: Look at $L_1 \setminus (L_2 \cap L_1)$. This one is ...
0
votes
2answers
2k views

Are supersets of non-regular languages also non-regular?

I have to proof that if $L_1 \subset L_2$ and $L_1$ is not regular then $L_2$ it not regular. This is my proof. Is it valid? Since $L_1$ is not regular, there does not exists a finite automata $M_1$ ...
9
votes
3answers
1k views

How to feel intuitively that a language is regular

Given a language $ L= \{a^n b^n c^n\}$, how can I say directly, without looking at production rules, that this language is not regular? I could use pumping lemma but some guys are saying just looking ...
5
votes
3answers
247 views

Length of mid part of the string in Pumping Lemma

This standard definition of pumping lemma from Wikipedia. Let $L$ be a regular language. Then there exists an integer $p\ge 1$ (depending only on $L$) such that every string $w$ in $L$ of length ...
1
vote
0answers
59 views

Show that a language is not regular using the Pumping Lemma [duplicate]

Possible Duplicate: How to prove that a language is not regular? Given a language $L = \{a^pb^{2p} \mid p \ge 1\}$, how could I show, using the Pumping Lemma that $L$ is not regular?
7
votes
1answer
5k 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 \...
7
votes
1answer
6k views

Relation between simple and regular grammars

I am reading "An Introduction to Formal Languages and Automata" written by Peter Linz and after reading the first five chapters I face below problem with simple and regular (especially right linear) ...
17
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 ...
3
votes
4answers
3k views

Why is $L= \{ 0^n 1^n | n \geq 1 \}$ not regular language?

I'm looking for intuition about when a language is regular and when it is not. For example, consider: $$ L = \{ 0^n 1^n \mid n \geq 1 \} = \{ 01, 0011, 000111, \ldots \}$$ which is not a regular ...
4
votes
2answers
619 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 ...
-2
votes
1answer
8k views

Regular expression for all strings with at least two 0s over alphabet {0,1}

My answer : (0+1)* 0 (0+1)* 0 (0+1)* Why is this incorrect? Can somebody explain to me what the correct answer is and why?
31
votes
2answers
2k views

Why is a regular language called 'regular'?

I have just completed the first chapter of the Introduction to the Theory of Computation by Michael Sipser which explains the basics of finite automata. He defines a regular language as anything ...
1
vote
1answer
429 views

Non-regular Languages? [duplicate]

Possible Duplicate: How to prove that a language is not regular? Why $L_a$ and $L_b$ are not reguluar? $L_a = \{ e^i f^{n-i} g^j h^{n-j} : n \in N, 1 \leq i, j \leq n \}$. $L_b= \{nm^{i_1} ...
4
votes
2answers
328 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
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

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{...
6
votes
4answers
365 views

Why does $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ generate a context free language for regular $L$?

How can I prove that the language that the operator $A$ defines for regular language $L$ is a context free language. $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$, where $x^R$ is the ...
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)=\{...
5
votes
1answer
267 views

Closure against the operator $A(L)=\{ww^Rw \mid w \in L \wedge |w| \lt 2007\}$

I would like your help with the following question: Let $L$ be a language, and operator $A(L)=\{\,ww^Rw \mid w \in L\ \wedge\ |w| \lt 2007\,\}$ where $x^R$ is the reversed string of $x$. Which of ...
5
votes
1answer
900 views

Chomsky normal form and regular languages

I'd love your help with the following question: Let $G$ be context free grammar in the Chomksy normal form with $k$ variables. Is the language $B = \{ w \in L(G) : |w| >2^k \}$ regular ? ...
24
votes
1answer
567 views

“Dense” regular expressions generate $\Sigma^*$?

Here's a conjecture for regular expressions: For regular expression $R$, let the length $|R|$ be the number of symbols in it, ignoring parentheses and operators. E.g. $|0 \cup 1| = |(0 \cup 1)^*| ...
3
votes
1answer
360 views

Null Characters and Splitting the String in the Pumping Lemma

So I'm really struggling with the pumping lemma. I think most of my problems come from not understanding how you can and can't split the string in a pumping lemma question. Here is an example, take ...
9
votes
4answers
2k views

Words that have the same right- and left-associative product

I have started to study non deterministic automata using the book of Hopcroft and Ullman. I'm stuck in a problem that I found very interesting: Give a non deterministic finite automaton accepting ...
4
votes
3answers
432 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, ...
47
votes
8answers
62k 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 ...
10
votes
2answers
2k views

How to prove regular languages are closed under left quotient?

$L$ is a regular language over the alphabet $\Sigma = \{a,b\}$. The left quotient of $L$ regarding $w \in \Sigma^*$ is the language $$w^{-1} L := \{v \mid wv \in L\}$$ How can I prove that $w^{-1}L$ ...
0
votes
0answers
112 views

Multiples of n is a regular language [duplicate]

Possible Duplicate: Language of the values of an affine function Let $C_n = \{x\mid x \text{ is a binary number that is a multiple of } n\}$. Show that for each $n$, the language $C_n$ is regular....
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 ...
14
votes
3answers
734 views

Number of words in the regular language $(00)^*$

According to Wikipedia, for any regular language $L$ there exist constants $\lambda_1,\ldots,\lambda_k$ and polynomials $p_1(x),\ldots,p_k(x)$ such that for every $n$ the number $s_L(n)$ of words of ...
72
votes
8answers
94k 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 ...
17
votes
4answers
7k views

Using Pumping Lemma to prove language $L = \{(01)^m 2^m \mid m \ge0\}$ is not regular

I'm trying to use pumping lemma to prove that $L = \{(01)^m 2^m \mid m \ge0\}$ is not regular. This is what I have so far: Assume $L$ is regular and let $p$ be the pumping length, so $w = (01)^p 2^p$....
6
votes
1answer
110 views

Regular sets have linear growth?

Is it true that the set $\{ 0^{n^2} \mid n \in\mathbb{N} \}$ is not regular because it does not grow linearly? Regular sets are called regular because if you have a regular set then you can always ...
4
votes
3answers
181 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$ ...
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 ...
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. ...
4
votes
1answer
215 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 = \...
18
votes
3answers
324 views

Is this language defined using twin primes regular?

Let $\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}.$ Is $L$ regular? This question looked suspicious at the first glance and I've realized that it is connected with the ...
11
votes
2answers
8k 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 ...
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: ...
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
5answers
2k views

A sufficient and necessary condition about regularity of a language

Which of the following statements is correct? sufficient and necessary conditions about regularity of a language exist but not discovered yet. There's no sufficient and necessary ...
23
votes
3answers
2k views

What are the conditions for a NFA for its equivalent DFA to be maximal in size?

We know that DFAs are equivalent to NFAs in expressiveness power; there is also a known algorithm for converting NFAs to DFAs (unfortunately I do now know the inventor of that algorithm), which in ...
13
votes
1answer
3k views

Is there a context free, non-regular language $L$, for which $L^*$ is regular?

I know that there are non-regular languages, so that $L^*$ is regular, but all examples I can find are context-sensitive but not context free. In case there are none how do you prove it?