We changed our privacy policy. Read more.

Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
18
votes
1answer
568 views

Exponential separation between NFAs and DFAs in the presence of unions

For a regular language $L$, its DFA complexity is the size of the minimal DFA accepting it, and its NFA complexity is the size of the minimal NFA accepting it. It is well-known that there is an ...
3
votes
3answers
2k views

Are regular and context free languages closed against making them prefix-free?

For a language L we define: $\qquad A(L) = \{ x \in L \mid \text{ no proper prefix of x is in L} \} $ Are regular / context free languages closed under this operation ? For regular languages I ...
-2
votes
2answers
501 views

How to do Big 'O' notations [duplicate]

How can I solve $\mathcal{O}$-notations without using Java or any other programming language? I only want to use pen and paper.
2
votes
0answers
71 views

Complement of non-deterministic finite automation [duplicate]

Given an NFA, is there a way to “take its complement” and obtain an NFA that recognizes the complement language?
1
vote
1answer
127 views

The language of all borderless words

Could anyone help me please to find who was the first person who has proved that the language of all borderless words is not regular and when was that? Could you mention the reference, please? A word ...
-1
votes
2answers
511 views

Binary regular language?

Given $m,n\in\mathbb{N}$, finite alphabet $A=\{a,b,c\}$, and $L=\{(a^m,a^n)\}^*=\{(a^{mk},a^{nk})|k∈N\}\subseteq A^*\times A^*$. Is this binary language $L$ regular over $A(2,\$)$ (i.e. $\{A∪\{\$\}\}\...
5
votes
1answer
2k views

Are HTML and CSS regular languages?

I have a question whether or not CSS and HTML are regular languages. I believe CSS is a regular language, since it should be possible to create a regular expression to match the structure of CSS. ...
14
votes
2answers
398 views

Is it decidable if a language described by number of occurences is regular?

It is known that the language of words containing equal number of 0 and 1 is not regular, while the language of words containing equal number of 001 and 100 is regular (see here). Given two words $...
10
votes
1answer
2k views

Is there a way to test if two NFAs accept the same language?

Or at least generate a set of strings that one NFA accepts, so I can feed it into the other NFA. If I do a search through every path of the NFA, will that work? Although that will take a long time.
2
votes
2answers
288 views

Closure of Star-Free Languages under Substitution

Let $L$ be a star-free language over finite alphabet $\Sigma$. A substitution will be a map $\sigma : \Sigma \to \mathcal{P}(\Sigma^*)$. It seems obvious that if $\sigma(a)$ is star-free for every $...
4
votes
1answer
3k views

What does the R superscript notation mean in regular/formal languages?

What does the capital R superscript notation mean in regular languages? I am working on a homework assignment and don't recall my professor mentioning what the what the R superscript means. For ...
5
votes
1answer
226 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?
0
votes
1answer
79 views

Regular language proving

Question:The set of all first names given to children born in New Zealand in 1996 I think this language is regular because every element in the set can be a accept state How can I prove if the ...
16
votes
4answers
2k 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 ...
0
votes
2answers
2k views

How to convert NFA with null moves to NFA without null moves?

I am converting NFA with $\varepsilon$-moves to the NFA without $\varepsilon$-null moves. I understand that if, there is a $\varepsilon$-move between, $q_i$ and $q_j$, then all edges from $q_j$ have ...
1
vote
3answers
9k views

Proof that the regular languages are closed under string homomorphism

Where can I find a proof of this? Thanks!
4
votes
5answers
56k 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
1k 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
1answer
359 views

k-basis representation of natural numbers

(This is the problem 1.56 from Michael Sipser' Introduction to the theory of computation ) Let $A_k(S)= \{ w |w \text{ is the k-basis representation}$ $\text{ without leading 0 of some natural number ...
7
votes
1answer
982 views

Is the language of binary representation of perfect squares regular?

Let $\mbox{bin}(n)$ denote the binary representation of an integer $n$. Let $L = \{ \mbox{bin}(n^2) \mid n \in \mathbb{N} \}$. Is $L$ a regular language? I think one can prove that $L$ is not ...
5
votes
4answers
2k views

Without using pumping lemma, can we determine if $A =\{ww \mid w \in \{0,1\}^* \}$ is non regular?

Without using pumping lemma, can we prove $A =\{ww \mid w \in \{0,1\}^* \}$ is non regular? Is $L= \{w \mid w \in \{0,1\}^* \}$ non regular? I'm thinking of using concatenation to prove the former ...
1
vote
1answer
97 views

Is the language $a^{3}b^{+}$ the same as $\{a^{3}b^{n}, n \geq 1\}$ ? and what is the result of pumping this?

The regular expression $a^{3}b^{+}$ is indeed regular because we can define an automata $M$. But I see that $\mathcal{L} = \{a^{3}b^{n}, n \geq 1\}$ may generate the same strings, but using the ...
5
votes
2answers
485 views

Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular

Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular. These are the things that I would use to start. As $L_1L_2$ is regular, then the homomorphism $h(L_1L_2)$ is regular. Let $h(L_1)...
28
votes
1answer
998 views

Asymptotics of the number of words in a regular language of given length

For a regular language $L$, let $c_n(L)$ be the number of words in $L$ of length $n$. Using Jordan canonical form (applied to the unannotated transition matrix of some DFA for $L$), one can show that ...
-1
votes
2answers
2k views

Using pumping lemma to show $L = \{a^i b^j a^k \ | \ k > i + j\}$ cannot be accepted by an FA

$L = \{a^i b^j a^k \ | \ k > i + j\}$ Use the pumping lemma to show that this language cannot be accepted by an FA. Proof: Suppose $L$ can be accepted by an FA. Suppose a string $s = xyz \...
0
votes
2answers
290 views

Proving $\{xx^R \mid x\in L_1, x^R\in L_2\}$ is context-free

I have this problem: Let $L_1$ and $L_2$ be two regular languages. Show that $L_3 = \{xx^r : x \in L_1, x^r \in L_2 \}$ is a context-free language. I am unsure how to prove that some language is ...
2
votes
1answer
48 views

Chomsky form for language of single alphabet member

I'm a bit confused as to how to represent the Chomsky form for the language L that generates all strings with the alphabet {a} My approach was ...
1
vote
1answer
733 views

Giving a regular grammar for the language

I am trying to brush up on my regular grammar knowledge to prepare for an interview, and I just am not able to solve this problem at all. This is NOT for homework, it is merely me trying to solve this....
9
votes
2answers
592 views

Regularity of the exact middle of words from a regular language

Let $L$ be a regular language. Is the language $L_2 = \{y : \exists x,z\ \ s.t.|x|=|z|\ and\ xyz \in L \}$ regular? I know it's very similar to the question here, but the catch is that it's not a ...
0
votes
1answer
2k views

Regular expression for odd binary numbers without leading zeros

I have to write a regular expression that accepts any odd binary number not preceded by a 0. the best I can come up with is $1(0\cup1)^*1$, but that doesn't match just 1. The best it matches is 11.
4
votes
1answer
13k 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?
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,...
3
votes
2answers
278 views

Does $c^*(b \cup (ac)^*)^*$ define all strings over $\{a,b,c\}$ that don't contain the substring $bc$

I'm reading my textbook and it claims that the regular expression $c^*(b \cup (ac)^*)^*$ defines the language $L$ over $\{a,b,c\}$ which consists of all strings that do not contain the substring $bc$. ...
6
votes
3answers
131 views

For regular languages A and B, determine whether B might match early in (A B)

I have two regular languages A and B, and I want to determine whether there is any pair of strings, a in A and b in B, such that (a b) is a prefix of a string in (A B) and the left-most ...
13
votes
4answers
3k views

Star free language vs. regular language

I was wondering, since $a^*$ is itself a star-free language, is there a regular language that is not a star-free language? Could you give an example? (from wikipdia) Lawson defines star-free ...
3
votes
2answers
408 views

Why is the subset of palindromes of a regular language context-free?

Why is $A(L) = \{x \in L \mid x = x^R \}$ context-free if $L$ is a regular language? Trying to understand the approach to determining whether a regular language is context-free.
0
votes
1answer
373 views

Pumping Lemma for regular languages proof doubt - Sipser Book

I was reading the proof of pumping lemma from Sipser's book. I couldn't understand certain things mentioned there. In the second paragraph he has written, "because $r_l$ occurs among first $p+1$ ...
2
votes
1answer
156 views

Deciding whether a given language is regular [duplicate]

I am struggling with a homework assignment. This next question seems to be pretty easy, once I get what I feel like I'm missing now. Anyway, here goes: Decide if the following language is regular ...
3
votes
1answer
3k views

Show that the Kleene star of any unary language is regular [duplicate]

An exercise asks me to show that the Kleene star of any unary language $L$ is regular. $E$ is the alphabet, $E = \{ 1 \}$ Here's my reasoning : $L$ is regular $\implies$ $L^*$ is regular (closure ...
3
votes
1answer
2k views

Can we say anything about the complement of a regular language?

Given a regular language $L$, can we say anything about its complement $\overline L$? One thing that is trivial to say is that the DFA's for both languages are equal in size as complementing the ...
4
votes
2answers
69 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
163 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 \\ ...
1
vote
2answers
15k views

Are the non-regular languages closed under reverse, union, concatenation, etc?

My question: do the non-regular languages have closure properties? For example, if the reverse of L is non-regular, then L is non-regular ? thank you :-)
3
votes
1answer
4k views

DFA to regular expression conversion

I was looking at the question How to convert finite automata to regular expressions? to convert DFA to regex. The question, I was trying to solve is: I have got the following equations: $Q_0=aQ_0 \...
2
votes
1answer
288 views

Is The Following Language Regular? [duplicate]

Let $L_{1}$ and $L_{2}$ be 2 languages over the same alphabet $\Sigma$. $$A(L_1,L_2)=\{x\in \Sigma^*|\exists y,z\in L_2\text{ such that } yxz\in L_1\}$$ Assume that $L_{1}$ is regular and $L_{2}$ ...
0
votes
1answer
1k views

Constructing right-linear grammar

Is the grammar $\qquad S \to 1A0A \mid 0A \mid \varepsilon$ a right-linear grammar? $A$ is a nonterminal here, $0$ and $1$ are terminals. I know $0A$ is right-linear but what about $1A0A$? Trying ...
5
votes
2answers
4k views

String of minimum length in $\{a, b\}^*$ not in a regular expression

I'm doing an exercise in my book, the question is to find a string of minimum length in $\{a, b\}^*$ not in the language corresponding to the given regular expression. a. $b^*(ab)^*a^*$ My answer: $...
1
vote
1answer
5k views

DFA Minimization: Finding all equivalence classes of $\mathsf{R_L}$ for language $011(0+1)^*011$

How do we find all equivalence classes of $\mathsf{R_L}$ for a language? Say I'm trying to look for all equivalent classes for the regular language $\mathsf{L}$ is $011(0+1)^*011$. Here's an ...
1
vote
1answer
2k views

How to apply the pumping lemma to $\{0^m 1^n \mid 2n \leq m \leq 3n, m,n \geq 0 \}$?

I'm not really sure the how you would go about proving this language isn't regular with the pumping lemma: $L= \{0^m 1^n | 2n \leq m \leq 3n, m,n \geq 0 \}$ Does this indicate that $S = 2$, so we ...
12
votes
2answers
3k 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 ...