Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,357
questions
0
votes
1answer
11 views
Pumping Lemma,regular languages
Lets say that we have the language L = { $a^n$$b^m$$c^{m+n}$ $|$ $m$,$n$ $>=0$ }
What is the way that i should follow to prove
that the language is not regular?
Assume that the language is ...
0
votes
1answer
25 views
validation of a pumping lemma proof for regular languages
I have the following regular expression:
Of course I could think of a word like $w=a^{m+2}b^{m+2}c^{2m+3}$ and continue with the proof BUT
I was just wondering, because $L$ is made up of a union of ...
0
votes
1answer
25 views
Proof that a language is not regular using the pumping lemma
I do not understand the last sentence of the proof provided. It says that the fact that xz does not belong to L contradicts the hypothesis, but isn't it that xyz not belonging to L what we are trying ...
0
votes
1answer
18 views
What is Pumping length for Union of Regular languages?
This is an exam question.
For E = {a,b}. let us consider the regular language
$L= \{x|x = a^{2+3k} or x=b^{10+12k}, k >= 0\}$
Which one of the following can be a pumping length (the constant ...
0
votes
1answer
65 views
Minimum pumping length of (01)*
Michael Sipser offers the definition:
The pumping lemma says that every regular language has a pumping length p, such that every string in the language can be pumped if it has length p or more. If p ...
0
votes
1answer
49 views
Is this language with prefix regular?
Is this language regular?
${w ∈ (a + b)∗ : |u_{a}|>= 2009 · |u_{b}|}$ for every non empty prefix $u$ of string $w$}
I think it's non-regular. I tried concatenation of $L_{prefix} $={${ u : |u_{a}|&...
2
votes
2answers
49 views
Prove that every regular subset of $a^nb^n$ is finite
How to prove that every regular subset of $L=\{a^nb^n \mid n\ge0 \}$ is finite?
I know that every finite language is regular, and it's not true that every regular language is finite.
I also know that $...
2
votes
3answers
1k views
Prove or Disprove: an infinite intersection of regular languages is a context-free language
Let $L_1, L_2,...$ and $L=\cap_{k=1}^{\infty}L_k$ be languages over $\Sigma ^{*}$.
Prove /Disprove: if $\forall k\in \mathbb{N} $, $L_k$ is a regular language, then $L$ is a context-free language.
I ...
2
votes
0answers
26 views
Regular string relations - proof of correctness
Let $T \subseteq \Sigma^* \times \Sigma^*$ be a regular (rational) relation. We define the obligatory rewrite relation over $T$ as follows:
$$
R^{obl}(T) := N(T) \cdot (T \cdot N(T))^*
$$
$$
N(T) := ...
1
vote
2answers
38 views
Regular of language of all words of length 3
Consider the language $$L = \{ x \in \{0,1\}^* \mid |x| = 3 \}.$$
I think the above language is regular. A DFA can be used to determine the above language.
Am I correct? Is the above language regular?...
0
votes
1answer
15 views
Convert the given NFA to DFA
I am trying to find an DFA for the regular language given by the expression $L\left( aa^{\ast }\left( a+b\right) \right)$.
First simplifying $L\left( aa^{\ast }\left( a+b\right) \right)$ we get
$L\...
1
vote
1answer
32 views
Number of equivalence classes
Given language $L$, why is it not necessarily true that the number of equivalence classes of $L$ is equal to the number of equivalence classes of $L^R$?
And for the private case that $L$ is regular, ...
-2
votes
0answers
34 views
Regular Expression and Finite Automata for the language of Odd-Odd
Regular Expression and Finite Automata for the language of Odd-Odd i.e. all string should contain odd numbers of x’s and y’s but in any order, assume the ∑ = {x,y}. For Example: xy, xxyxyy, xyxyxy, ...
1
vote
1answer
22 views
Why Right-Division of regular language with RE\E language is regualr?
I think I can't understand the meaning of language being decidable.
The next case makes no sense to me:
Considering I have language L1 which is regular, and language L2 which is in RE\R (in ...
1
vote
1answer
42 views
necessary and sufficient pumping lemma - bounded pumping variant
There exists a variation of the pumping lemma with necessary and sufficient conditions for a language to be Regular.
According to that lemma:
A language $L$ is regular iff $\exists k$, $\forall x\in ...
0
votes
1answer
65 views
Is this language L regular?
Let's say we have the language L = {w $\in$ {a,b}$^*$ : ($\exists n \in \mathbb{N} $)[$w|_b = 5^n$]}. I want to know if this is a regular language or not. How do I go about doing this? I'm familiar ...
0
votes
1answer
30 views
Complement of $0^n1^n | n \in \mathbb{N}$
I know why A is irregular by Closure properties of irregular language. I also know the complement of $ \{ 0^n 1^n | n \in \mathbb{N}\}$ is $A = \{ 0^i 1^j| i \neq j\} \cup (0 \cup1)^*(1)(0 \cup1)^*0(0 ...
-1
votes
1answer
36 views
How to show that a language is regular
I know that to show that a language is not regular, you are supposed to use the pumping lemma, but I cannot figure out how can I show that a language is regular.
How would I show that the following ...
-3
votes
1answer
34 views
Construct regular expression for given language
How to construct regular expression for language L={a,b,c} which contain all words starts with bab and ends with babc?
-1
votes
0answers
27 views
Is language bin(n)bin(2^(k+1) n + 1)^R context-free
I have a problem with this exercise. For language $$L_1 = \{ w \in \{0, 1\}^* : \exists k \in \mathbb N \ w = \text{bin}(n)(\text{bin}(2^{k+1}n + 1))^R \},$$ where $\cdot^R$ reverses a string and $\...
3
votes
1answer
39 views
Minimum pumping length of concatenation of two languages
there's this small part of my homework that I just can't figure out.
Let us denote $p(L)$ as the minimum pumping length of some language $L$. I'm supposed to find two regular languages $A,B$ so that
...
3
votes
1answer
56 views
Finding the upper bound of states in Minimal Deterministic Finite Automata
I have a task to determine the upper bound of states in the Minimal Deterministic Finite Automata that recognizes the language: $
L(A_1) \backslash L(A_2) $, where $ A_1 $ is a Deterministic Finite ...
0
votes
1answer
21 views
When proving a set is not regular is it enough to prove a subset of it regular?
E.g. when proving L = {w in {a,b}^*: the first, the middle, and the last characters of w are identical}, can i just prove ab^pab^pa is not regular? Where p is the pumping length?
0
votes
1answer
21 views
How to define an automata for zig zag concatenation? [duplicate]
I have two DFAs one for language A and one for language B.
I'm asked to make an FDA that is the zig-zag concatenation of letters of A and letters of B.
This is described by the following: {w: w = $a_1 ...
1
vote
1answer
70 views
Zigzag concatenation of two languages
Given two regular languages $A,B$ on the same alphabet $\Sigma$, I want to show that the following language is regular:
$$
\{a_1b_1 \ldots a_kb_k \in \Sigma^* \mid a_1,\ldots,a_k,b_1,\ldots,b_k \in \...
1
vote
2answers
149 views
Given regular language $L$, is $L_1 = \{ w \mid \text{each prefix of } w \text{ of odd length} \in L \}$ regular?
I was given a question and don't really know to solve it.
Given a regular language $L$, is the following language also regular?
$$L_1 = \{ w \mid \text{each prefix of } w \text{ of odd length ...
1
vote
3answers
291 views
$a^*b^*c^* \setminus \{a^n b^n c^n | n ≥ 0\}$ is not regular using pumping lemma?
$L=a^*b^*c^* \setminus \{a^n b^n c^n \mid n \geq 0\}$ can be proved as context-free by partitioning it as $L = \{a^nb^mc^* \mid n \neq m\} \cup \{a^*b^nc^m \mid n \neq m\}$ and further dividing each $\...
3
votes
1answer
100 views
Why is this language a regular language?
Came across this in a book, and I'm wondering why the following language is regular?
$$ L = \{a^nww^R: n \geqslant 0, w \in \{a,b\}^3\}$$
Is it correct to say that $$ \{a^n : n \geqslant 0\} $$ is a ...
0
votes
2answers
39 views
Regular expression for a palindrome of finite length?
I have a language $$ L = \{ww^R, w \in \{ab\}^5\}$$
I know this is a regular language because it is finite (since w can only be of length 5). I want to prove it's a regular language, so I'd create a ...
1
vote
1answer
19 views
I'm asked to draw DFA for this {$\epsilon$, 0} however I do not understand what {$\epsilon$, 0} mean
I'm asked to draw a DFA of this {$\epsilon$, 0} but have no clue what it means. Can someone help me understand what the automata is supposed to do?
I know that $\epsilon$ is the symbol for empty ...
1
vote
2answers
23 views
can more than two arrows point towards the same state from other states in a DFA?
Is something like this possible:
You have state A,B,C all pointing towards accepting state D.
Is this allowed?
Where online can I find a list of rules that define how an automata must be drawn or ...
0
votes
0answers
41 views
Prove that all regular language is in L
im looking for a formal proof to demonstrate that all regular language is in L (logarithmic space).
I deduced that all regular languages has a DFA that accept them, so if i find a way to transform all ...
0
votes
1answer
31 views
$\text{DSPACE}(O(1))=\text{REG}$ Proof?
I want to know why $\text{DSPACE}(O(1))=\text{REG}$, especially in the direction of why all languages in $\text{DSPACE}(O(1))$ can be recognized by a finite automaton. I've thought for some time and ...
-1
votes
1answer
31 views
Automata that respect the condition {w|w contains at least two 0s and at most one 1}
we have the alphabet {0,1}.
{w|w contains at least two 0s and at most one 1}
It tried this: (However I'm not sure if it's correct. If it's incorrect why?)
0
votes
1answer
29 views
I'm trying to understand DFAs is my DFA correct in this question if not why?
I have the following alphat {0,1}.
I'm told to draw a DFA which fulfills the following: {w|w starts with 1 and ends in 0}
This is the DFA I came up with.
1
vote
1answer
35 views
How to create a regular expression for this language?
I have a language:
$$ \{a^jb^k \mid j \neq k \text{ and } j \equiv k \pmod 3 \}$$
I want to prove that this language is regular. My first thought was to create a regular expression that accounts for ...
0
votes
2answers
51 views
Is it possible to design a Turing Machine without extra symbols for this language?
Is it possible to design a Turing Machine for the language defined as L = {0n1n | n >= 0} with only the symbols in the set of {blank, 0, 1}?
1
vote
0answers
24 views
$L = \{\alpha^i \beta^j \gamma^k \vert i,j,k \in \mathbb{N}_0, (i=1) \Rightarrow (j=k)\}$
I am asking this question here, because I am not allowed to comment on the thread that I am actually interested in, but maybe someone can still help me?
I alredy found an anwser to the Problem above (...
2
votes
1answer
53 views
Two-way finite automaton: How does the automaton remember the state
I have been going through a theory of Two-way finite automatons and I did not understand the given example when there were a DFA A = (Q, Σ, δ, q1, F). the 2-DFA B = (Q ∪ Q| ∪ Q|| ∪ {q0, qN, qF}, Σ ∪ {#...
2
votes
1answer
28 views
Regular language as finite union of periodic sets
Is it true that every regular language can be expressed as a finite union of periodic sets? In other words, if $L$ is regular, then do there exist finite sets $A_1,\dots,A_n,B_1,\dots,B_n$ such that
...
0
votes
2answers
91 views
Is a language regular
Given a regular language $L$ (so there is an automaton $A$ which recognizes $L$), I need to determine whether $ L'$ is also regular, where $L'$ is given by
$$ L' = \{ \alpha \in \Sigma^* \mid (\...
0
votes
0answers
21 views
Natural Languages
Can one imply that natural languages can be described by regular grammar? Is that what happens through NPL? Trying to understand the subject of how spoken language can be converted to data and how.
1
vote
2answers
122 views
Given regular languages $L$, $M$. Is $K=\{uw | u,w \in \Sigma^*,(\exists v \in M) uvw \in L\}$ necessarily regular?
Question is as follows: Given regular languages $L$, $M$. Is $K=\{uw | u,w \in \Sigma^*,(\exists v \in M) uvw \in L\}$ necessarily regular?
Thank you for any input.
1
vote
0answers
35 views
How to generate a DFA that recognizes a non-regular Grammar
How would you convert the following grammar to a DFA that recognizes its language?
\begin{align}
&G = (\{S,A,B\},\{0,1\}, S, P)\\
&P\colon
&&S\rightarrow A1B\\
&&&A \...
1
vote
1answer
55 views
Prove that a finite language is regular
I want to prove that $L(G) = \{01; 11110; 10101; 000\}$ is regular.
Is it correct if I write there exists a regular expression, which is: $(01|11110|10101|000)$?
How can I also prove it using a DFA?
1
vote
1answer
71 views
Checking whether union of two languages is regular
How to check if
$L = \{c^ka^nb^n \mid k>0 \wedge n\geqslant0\} \cup \{a, b\}^*$
is regular ,where
$L_1 = \{c^ka^nb^n \mid k > 0 \wedge n\geqslant0\}$ is clearly not regular and $L_2 = \{a, ...
0
votes
1answer
26 views
Language of words whose run lengths are all distinct
Assume $ \Sigma=\{0,1\}$, is $L$ a regular language? If it is not, how should we prove it with pumping lemma?
$$L = \{1^{a_1} 0^{a_2}\ldots 01^{a_k} \mid k \in \mathbb N , a_i \geq 0 , \text{ the $...
-2
votes
1answer
19 views
Several closure operations for regular languages
Assuming that $L_a$ is a regular language and $\Sigma=\{0,1\}$, prove that the following languages are regular:
$$L_1 = \{u \mid \exists v\in\Sigma^* \, uv \in L_a\}$$
$$L_2 = \{w \in \Sigma^* \mid \...
2
votes
3answers
561 views
Bitwise XOR of regular languages
Is the language consisting of the bitwise XOR of elements of two regular languages still a regular language?
For example, consider
$$L=\{ x \operatorname{xor} y \mid x \in A, y \in B, |x|=|y| \},$$
...
0
votes
1answer
84 views
Proof language A= { 0^i 1^j where j>(i mod 3), j ≥0 , i≥0} is regular language
$A = \{0^i1^j \text{ where }j>(i \text{ mod }3), i \geqslant 0, j \geqslant 0\} $
I know that A is a regular language, since we can construct the DFA or the NFA, but i dont know how to construct ...
