Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,175
questions
0
votes
0answers
10 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 ...
28
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
34 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
21 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
41 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
45 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
93 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
99 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
31 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
51 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
61 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
42 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
51 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
36 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
25 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
47 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
39 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
84 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 ...
0
votes
2answers
82 views
Prove that the following language is regular [duplicate]
Let L1, L2 be regular languages. And let A1=〈Σ,Q,q0,𝛿1,F1), A2=〈Σ,P,p0,𝛿2,F2) be their DFA.
Prove that the following language is regular, by making an appropriate NFA for it:
𝐿3={𝜎1𝜎1′𝜎2𝜎2′…𝜎...
3
votes
1answer
50 views
Is there an algorithm to overapproximate a context free grammar by a regular expression?
I understand that a context-free grammar is strictly powerful than a regular expression in that a context free grammar can represent any regular language, but not all context free languages can be ...
