Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,157
questions
1
vote
1answer
47 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
51 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
88 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
22 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
21 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
36 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
52 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
44 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
18 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
23 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
46 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
41 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
52 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
49 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
84 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
102 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
31 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
62 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
38 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
53 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
47 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 ...
0
votes
2answers
65 views
Proving that L is not regular using closure properties
I need to show that the following language is not regular.
$$L = \{\ ab^jc^j\ |\ j \geq 0\ \}\ \cup\ \{\ a^ib^jc^k\ |\ i, j, k \geq 0 \ and\ i \neq 1\ \}$$
There is also a hint that it cannot be ...
0
votes
1answer
27 views
How to show a language is regular through creating DFA
I'm trying to prove that a given language is regular through proving that a DFA can be created from it, but have problems with how to the DFA should look.
The alphabet is $\Sigma=\{0, 1\}$ and the ...
0
votes
1answer
30 views
Constructing a DFA $M$ such that $L(M) = L(A) \bigtriangleup L(B)$ with a kind of log-space TM
Suppose that $A$ and $B$ are DFAs. We know that there is some DFA $M$ such that $L(M) = L(A) \bigtriangleup L(B)$, the symmetric difference. Also, we can construct this $M$ by some Turing machine $N$. ...
1
vote
1answer
311 views
Language whose intersection with a CFL is always a CFL
Prove or disprove: If the language $L$ is such that for every context-free language $L_0$, the language $L \cap L_0$ is context-free, then $L$ is regular.
I haven't managed to prove this, but I'm ...
1
vote
1answer
72 views
Prove that $L = \{ xy \in \{a , b \}\textbf{*} \mid |x|_a = 2|y|_b \}$ is not regular
Prove that $L = \{ xy \in \{a,b\}^* \mid |x|_a = 2|y|_b
\}$ is not regular.
I have already tried to prove it by using the pumping lemma and reduction to absurdity, but have been unsuccesful on both. ...
1
vote
3answers
339 views
Why is this basic language not a regular language?
L = {x in {0,1}* | x has an equal number of 0s & 1s}
Based on the recursive definition of regular languages, isn't it possible to form a single regular language set over the binary alphabet {0,1} ...
3
votes
1answer
91 views
Is the language of words with equal number of 010s and 101s as substrings regular?
Is the language of words containing same number of 101s and 010s regular?
If yes, how can I design a DFA for it?
In general, is the language of words containing equal number of strings which one is "...
6
votes
2answers
1k views
Is there a reasonable and studied concept of reduction between regular languages?
Have been any interesting formulations for the concept of reduction between regular langauges, and if so -- are there regular-complete languages under those reductions?
0
votes
1answer
45 views
Prove that the language is not regular [duplicate]
Prove that the following language $Σ = \{1\}$ is not regular.
$L$ = $\{w | |w| = k$, where $k$ is a prime number}.
How should one go about proving this? Should I use pumping lemma for this?
4
votes
1answer
265 views
Irregularity of language of prefixes of decimal expansion of pi
Let $L_{\pi}$ be the language consisting of prefixes of the decimal expansion of $\pi$:
$$L_\pi = \{3, 31, 314, 3141, 31415, 314159, \ldots\}.$$
Prove that Lπ is not DFA-recognizable. You may use the ...
0
votes
2answers
46 views
Regularity of a language contains more 1's than 0's
The language of all bitstrings with more 1s than 0s, i.e.,
$ A = \{x: 2\Sigma_{i}^{|x|} x_{i} > |x|\}$ is regular.
I know I should apply Pumping Lemma and the proof as well, what I cannot ...
1
vote
1answer
23 views
I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }
I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }. What does the " || " mean I know a single " | " means or.
-1
votes
1answer
39 views
Regular expression for all possible strings. Does the Kleene star distribute over each element. (0+1)* = 0* + 1*?
Regular expression for all possible strings. Does the Kleene star distribute over each element. Is this true? (0+1)* = (0* + 1*) ?
0
votes
1answer
58 views
Confused about pumping lemma, What i'm missing? [duplicate]
When I apply pumping lemma on this language:
${L=\{010^n:n\ge0\}}$ over the alphabet ${\Sigma =\{0,1\}}$ I get that it is non-regular despite the fact that it is regular.
let ${n=4}$, then $w=010000$...
0
votes
2answers
49 views
Show $\{1^n0^m |\space n \neq 2^m\}$ not regular using pumping lemma
Showing that the language $L$ with $\{1^n0^m |\space n \neq 2^m\}$ is not regular using Myhill-Nerode is easy: Let $i, j\in \mathbb{N}.i\neq j.$ It follows $1^{2^i}\nsim 1^{2^j}$ because $1^{2^i}0^{i}...
0
votes
0answers
38 views
construct regular expression for a language [duplicate]
I want a regular expression for the following language.
(a+b+c)*, but does not contain substring "abab".
That means it can be any combination of (a, b, c) except "abab".
I tryed to construct it ...
0
votes
2answers
58 views
Regular grammar with at most one c
I am attempting to make a regular grammar over alphabet {a, b, c} where there is at most one c. So far, I have the regular expression ((a|b)*|c)(a|b)* but am unsure ...
3
votes
1answer
67 views
Automaton recognizing ambiguously accepted words of another automaton
Let $A$ be a nondeterministic automaton. Let $X(A)$ the set of words for which there at least two accepting paths.
In one of the previous exam, for which no answers are available, it is required to ...
1
vote
2answers
50 views
DFA & RE from descriptive definition of given regular language
I am trying to make the DFA and RE of a regular language which is define on the alphabet = {1,0} and all the strings present in these languages have exactly one 010 substring in them.
Some strings ...
