Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
34 views

Automata with minimal number of states using reverse

So, by the Bzozowski theorem, if A is DFA det(rev(det(rev(A))) would have minimal number of states. And for the most of them work. But for this example, I can't figure out why it doesn't. I have an ...
0
votes
1answer
20 views

Examples of Regular, Context-free and Context-sensitive languages

Assume the languages: $$ a) \, L_1 = \{ w \in \{b,c \}^* | \, w \, \text{contains 'bbc' as substring} \} $$ $$ b)\, L_2 = \{ 1^k 0^m 1^m | k,m \in \mathbb{N} \} $$ $$ c)\,L_3 = \{ w \in {0,1}^* | \,...
0
votes
0answers
13 views

Given a DFA M, formally define an NFA N such that L(N) = {x in L(M) | x = reverse(x)}

The english description of the question is (from my understanding) N accepts all strings that are both palindromic (the same forwards as it is backwards) and accepted by M. After a lot of toil and ...
29
votes
2answers
1k views

Planar regular languages

In my class a student asked whether all finite automata could be drawn without crossing edges (it seems all my examples did). Of course the answer is negative, the obvious automaton for the language $\...
1
vote
1answer
35 views

Prove that a language is bounded if and only if it's finite

Let's assume $L$ is a language. $L$ is bounded if for some natural number $n \in \mathbb N$ applies $|x| ≤ n$, where $|x|$ is a length of a string, with every $x \in L$. Let's also assume that $L$ ...
-1
votes
0answers
15 views

L' = { w | ww ∈ L where L is regular } [duplicate]

Let L be a regular language. We define another language L' = {w | ww ∈ L} . Show that L' is regular. I was trying to construct an automaton for L' but unable to construct it. Please help or please ...
0
votes
0answers
23 views

Uncommon case in Arden's lemma $q_{2} = 1q_{2} \cup 0q_{2}$

I'm trying to get the regular expression of an automata but an state has a form that I don't know how to solve, the form on its simplest example is: $$q_{2} = 1q_{2} \cup 0q_{2}$$ What's the ...
8
votes
0answers
42 views

Regularity profiles

A standard exercise in formal language theory uses Lagrange's four-square theorem to construct a language $L$ such that $L$ isn't regular but $L^2$ is regular. (Let $A = \{ a^{n^2} : n \geq 0 \}$. ...
0
votes
0answers
31 views

If $L^2$ is regular. Does that imply L is regular [duplicate]

If $L^2$ is regular. Does that imply L is regular. I think L need not be regular. But I can't find any example where L is not regular but $L^2$ is regular. My teacher told me an example where L={$0^...
0
votes
1answer
36 views

Create automata from non regular grammar

I have two grammars: L → ε | aLcLc L → ε | aLcLc | LL This two grammars are equals but the first one is regular, so it produces a regular language and a ...
0
votes
0answers
46 views

How to prove this language is not regular?

I am currently learning Pumping Lemma and found this question. But I am not able to prove it not regular. L = { $0^n$ | n is power of 2}. So, here I considered w = $0^{2^n}$ where n is constant of ...
0
votes
0answers
24 views

Is there a language that pumps, but is not regular? [duplicate]

I'm looking for a concrete language that can be pumped but is not regular. I understand that closure properties can be used to further test if a language is regular/nonregular.
1
vote
2answers
95 views

How do i tell if a grammar is regular or not?

I know that a regular grammar has a definition $$\begin{align}S &\to aS\\ S &\to \lambda \end{align}$$ But I dont really know how to apply this information to check whether or not a grammar ...
0
votes
0answers
19 views

A deterministic finite state automata for finding all (potentially overlapping) regular expression matches?

I was working on a bioinformatics practice problem named Finding a Protein Motif on rosalind.info. In essence, I was given a particular regular expression ...
0
votes
1answer
24 views

Condition in Arden's rule

According to Arden's rule, the language equation $X= AX\cup B$, with unknown $X$, has the solution $X=A^*B$, provided $A$ does not contain the empty string. My question: what is the problem with the ...
1
vote
1answer
64 views

Determining equivalence classes of $\{w \in \{0,1\}^*\mid$ the $k$-bit of $w$ from the right is 1$\}$

I want to formally write the equivalence classes of the following language: $$L_k = \{w \in \{0,1\}^*\mid\text{ the } k\text{-th bit of }w\text{ from the right is } 1\}$$ I understand the definition ...
2
votes
2answers
101 views

Proof: There exists an irregular language L such that LLLL is regular

As title. I consider finding a specific L to fulfill the condition stated to prove the statement, however, I have no luck in finding one. A senior gave me a hint that Lagrange's four square theorem ...
1
vote
1answer
32 views

Pumping lemma regarding {a^2k w | w ∈ {a, b}*, |w| = k}

I had a question regarding the Pumping lemma for regular languages, I have been studying for an exam and came across the question {a^2k w | w ∈ {a, b}*, |w| = k}. In the website it lists the answer ...
-2
votes
1answer
37 views

Regular Expression: Writing an expression with at least two characters in length? [closed]

A past exam question: (1) Consider the language, $L$, of strings over the alphabet $\{x, y\}$ of length at least 2 with the second symbol being $x$. For example, $yx$, $xxyy$, and $yxy$ are members ...
-1
votes
1answer
15 views

Is finite subset of a set which contains all non regular languages a regular set?

Let A be a set which contains all non-regular languages. Then set B which is finite subset of A. Then will it be regular ? I know that A is not recursive enumerable set (undecidable). So I wonder ...
2
votes
1answer
40 views

How can the union of two 'context-free but not regular' languages be regular?

I cannot understand how the union of two languages which are context-free but not regular, can result in a regular language: If $L_1$ and $L_2$ are 'context-free but not regular' languages, defined ...
1
vote
1answer
52 views

How to characterize equivalence classes induced by Myhill-Nerode theorem?

Given $L=\lbrace w\in \lbrace 0,1 \rbrace^\ast : N_0(w)=N_1(w) \rbrace$, where $N_0(\cdot)$ and $N_1(\cdot)$ mean the number of zeroes and ones respectively, I need to characterize the classes ...
1
vote
1answer
64 views

Meaning of L* if L is a language

I can't find anywhere the meaning of $L^*$, given that $L$ is a language. I know $^* $ means repetition, for example $0^*$ = $\{ \epsilon, 0, 00, 000, \dots \}$. Or if $A$ is an alphabet $A^*$ are all ...
3
votes
2answers
98 views

Converse of pumping lemma for regular expressions

I want to come up with a language that satisfies the pumping lemma while not being a regular expression. I thought of $\{0^i1^j: i > j > 0\} $. The pumping seems to work just fine, and this is ...
0
votes
0answers
18 views

regular expression with kleene closure [duplicate]

my question is if my regular expression R is 1* that means the language accepted is {^,1,11,111,1111...} in that case i don't understand the meaning what (R*)* means
0
votes
1answer
23 views

Counting number of states from a regular expression

Given the regular expression: $r=ab+((a+\epsilon)c^*)^*$. Let A be a non-deterministic automaton that accepts the language of r. How many states are in A? Answer the question without building A ...
1
vote
1answer
24 views

A deterministic FA for $0^*1^*$ is required

A deterministic finite automaton without $\epsilon$ steps for the language $0^*1^*$ is required. Any nice picture ? I have created a NFA for this language which has 2 states $Q_1,Q_2$, both are ...
2
votes
1answer
44 views

Is $L(G) \subseteq L(R)$ decidable?

Is the following problem decidable? Given a context-free grammar $G$ and a regular expression $R$, is $L(G) \subseteq L(R)$? It is given that the following problem is undecidable Given a ...
1
vote
1answer
53 views

Can the difference of a non-regular and a regular language be regular?

I have some trouble understanding some exercises related to operations on regular languages.I tried to apply their closure properties, but I am not sure how to do the following exercises: If $L_2,L_3$...
2
votes
2answers
53 views

Is the language L = {(a,b)* | #a * #b is an odd number} regular?

Is the following language regular? $$\{ w \in \{a, b\}^* |\ \text{the product of the number of $a$'s and the number of $b$'s is an odd number}\} $$ If i'm not mistaken the condition is the same as ...
0
votes
2answers
37 views

Using pumping lemma to prove irregularity of regular language - what is my error? [duplicate]

I have a vital misunderstanding of the pumping lemma. In the following example I show an example of using it on a regular language to come to incorrect conclusions. What am I doing wrong? L={ab}, ...
2
votes
1answer
44 views

Construct a DFA from the regular expression (a)*+(aab)*

I've broken down the expression into two simpler DFAs but right now I'm stuck. I don't know what to do with the expression a*, my solution currently (as presented above) is a NFA, not DFA.
2
votes
1answer
20 views

Proving a language comprised of 2 languages is regular(with suffix and prefix)

I am having hard time proving that the following language,comprised from two regular languages $L_1,L_2$(over the same $\Sigma$)is indeed regular: $$L^\frown = \{ w\in \Sigma^* | w=u\sigma_1\mu_1...\...
4
votes
1answer
27 views

Proving a language comprised of 2 languages is regular

So glad to find this place. I have been struggling for quite a while with this given question and i am not sure how to fully address it. The question: $L_1$ and $L_2$ are regular languages over 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 ...
1
vote
0answers
25 views

Tree languages regular

Let $T_1,T_2 \subseteq T_\Sigma$ be regular tree languages, f a symbol with arity 2. To proof: $\{f(t_1,t_2) \mid t_1 \in T_1, t_2 \in T_2\} \subseteq T_{\Sigma \cup \{f\} }$ is regular. So it's ...
2
votes
1answer
48 views

Regularity of infinite concatenation

It is well-known that an infinite union of regular languages is not necessarily regular, since every language can be written as a union of singletons. What about infinite concatenations? Let $\{ L_z :...
1
vote
1answer
54 views

Construction of a Deterministic Tree Automaton (DTA)

Let $L \subseteq \Sigma^*$ be a regular language. Let $\Sigma' = \Sigma_0 \cup \Sigma_2$ where $\Sigma_0 =\Sigma$ and $\Sigma_2=\{*\}$. We define $T_L=\{t \in t_{\Sigma'} \mid \text{The leafs from t ...
3
votes
1answer
52 views

Complement of language $\{ x \in \{a,b,c,d\}^* : \exists$ prefix $y$ of $x$ such that $||y|_a - |y|_b|\leq 10 \}$

Is the complement of the following language a regular language? $$L = \{ x \in \{a,b,c,d\}^* : \exists \text{ prefix }y\text{ of }x\text{ such that }||y|_a - |y|_b|\leq 10 \}$$ My first thought is ...
2
votes
1answer
10 views

Regular expression notation clarification

For the alphabet $Σ$={a,b,c} I was wondering how you would say: T that has elements from Σ, so could be T=a, T=bc I was considering maybe $Σ^*$ or $Σ^+$ would describe that, but I am not sure ...
0
votes
0answers
31 views

Pumping lemma for regular languages confirmation

I have the language $\Sigma = \{0,1,+,= \}$ and $$\mathrm{ADD} = \{x = y + z \mid \text{$x$, $y$, $z$ are binary integers and $x$ is the sum of $y$ and $z$}\}$$ And with the pumping lemma I find what ...
2
votes
1answer
88 views

Finding a regular expression of a language

Our alphabet is {a,b} and we need to find a regular expression for the language of all words of the form $a^*b^*$, whose length is a multiple of 3. Obviously $(aaa)^*(bbb)^*$ is one of the options, ...
3
votes
3answers
103 views

Does $L_1L_2 = L_2L_1$ imply $L_1 = L_2$?

Let $L_1, L_2 \subseteq \Sigma^*$ be two languages, where $\Sigma$ is some finite Alphabet. Does $L_1L_2 = L_2L_1$ imply $L_1 = L_2$? What if $L_1$ and $L_2$ are regular languages? Can you give ...
0
votes
0answers
26 views

Using Nerode theorem to prove that the following languages are non-regular

I've been trying to understand the idea behind proving a language is not regular by using Nerode's theorem, but I just couldn't apply the idea on what I've been asked. The problem is to prove the ...
1
vote
1answer
48 views

Closure properties of a non-regular language under complement? [duplicate]

Assume I have L1 which is a regular language, so we know since regular language is closed under complement, the complement of L1 is also a regular language. But let's say if the complement of L1 is a ...
2
votes
1answer
22 views

Does |xy| ≤ p in the pumping lemma count for all i?

While learning about the pumping lemma, I came across the following question: Given the language L is $ a^n(0|1)^* $ with $ c_0 \cdot c_1 = n $, where $ c_0 $ indicates the amount of zeros present, ...
2
votes
3answers
87 views

proving L1* ∪ L2* ⊆ (L1∪L2)*

x∈ L1* ∪ L2* ⇔ x∈ L1* ∨ x ∈L2* ⇔ x ∈(L1)* ∨ x∈(L2)* ⇔ x ∈L1* ∪ L2* ⇔ x∈(L1∪L2)* Is it enough to prove it this way?
1
vote
1answer
38 views

Proving that the set of grammars generating L or L complement is undecidable

Let $X$ be a regular language, I need to prove that either $\{G \mid L(G) = X\}$ or $\{G \mid L(G) = \overline{X} \}$ is undecidable using the following hint: Use reduction to absurdity supposing that ...
0
votes
1answer
39 views

Recognizing Regular Languages in Layman terms [duplicate]

I understand that regular languages are languages which can be computed by Finite Automata however i am having some trouble understanding how one can identify a regular from non-regular. I know that ...
9
votes
1answer
1k views

Non-deterministic Finite Automata | Sipser Example 1.16

I am working through the Sipser Book (2nd edition) and came across this example, which I do not understand. In the book it states that this NFA accepts the empty string, $\epsilon$. Could someone run ...