Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,817
questions
1
vote
1
answer
84
views
Is regular expression syntax regular?
Regular expressions are equivalent to DFA's and describe regular languages, but is the language used to construct regular expressions regular?
My guess is that the original syntax (concat, | and *) ...
1
vote
1
answer
152
views
DFA for $L=\{w: w\in \{a,b\}^*, |w|_a\ \equiv |w|_b \equiv 0$ $(mod$ $5) \}$
There is a language:
$L=\{w: w\in \{a,b\}^*, |w|_a\ \equiv |w|_b \equiv 0$ $(mod$ $5) \}$. My idea for DFA is - we count number of $a$$\pmod{5}$ and separately we count number of $b$$\pmod{5}$. So we ...
1
vote
2
answers
1k
views
composite number Pumping Lemma for L = {$0^p$∣$p$ is a composite number} [duplicate]
Consider the language $L = \{0^p \mid p \text{ is a composite number}\}$.
I know that this is not a regular language. I have thought that to prove this language is not regular take the complement (...
1
vote
1
answer
223
views
Size of intersection of two acyclic DFAs A and B is O(|A|+|B|)?
Acyclic DFAs recognize finite languages. For more info, see this Wikipedia page : https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_state_automaton
To explain that the product of two DFAs $A$...
1
vote
1
answer
54
views
Terms and definitions for regular language and NFA
let's say L is a regular language,what term does L should uphold so that there is an NFA without epsilon moves,in which for every accepting state δ(q,σ)=Ø?I can think of some terms like that the last ...
1
vote
1
answer
99
views
If $R,F \cap R, F \cap \overline{R}$ are regular, is $F$ regular?
Let $R \in REG$. Is it true that if $F\cap R \in REG$ and
$F \cap \overline{R} \in REG$ then $F \in REG$?
I took $R = \Sigma^{\ast}$ and because $F\cap R \in REG$, $F$ must be regular. Is this the ...
1
vote
1
answer
90
views
Does a language have a regular expression if and only if it is regular? [closed]
I know that if a language has a regular expression it is regular, is the other way also true?
1
vote
1
answer
733
views
Does a given e-NFA accepts all the Strings?
Given an e-NFA. It is easy to find a string that is accepted by it. But, how do we find if the given e-NFA accepts "All" the strings over the alphabet. Or if there is a string that is not accepted by ...
1
vote
1
answer
221
views
Show language is not regular
Show that the following languages are not regular in two ways: first by using
closure properties then by using the Pumping lemma:
$$\text{(1) L1} = {a^n b^k c^{n+k} : n >= 0; k >= 0}$$
$$\text{...
1
vote
1
answer
635
views
Regular languages and constructing a regular grammar
I'm pretty new to computer science and just read about the concept of grammars. Now, I have a practical problem to solve. Here is the alphabet {a, b, c, d}.
How ...
1
vote
1
answer
552
views
Finding regular expression for a language with more substring of one type than from another
Take the alphabet A={0,1} I need to build a regular expression for the language with less or equal substrings 011 than 110.
I tried to figure out what would be the finite automata but I'm not to ...
1
vote
1
answer
2k
views
What is the minimum pumping length of the following languages?
How to determine the minimum pumping length of union of two languages? How do I proceed after determining the individual pumping lengths?
0*1+0+1* U 10*1 - Here the minimum pumping length of the ...
1
vote
1
answer
660
views
Why do non regular languages have infinitely many equivalence classes?
For example, for the language $L = \{a^nb^m|n \neq m\}$, why does it have infinitely many equivalence classes? How do I show/see that?
1
vote
1
answer
28k
views
Is this language regular or non-regular: {ww : w ∈ {a,b}* } [duplicate]
This is a question from a text book that's giving me some trouble. The question is:
Determine whether or not this language is regular. Justify your answer.
$$L = \{ww : w \in \{a,b\}^* \}$$
I ...
1
vote
2
answers
85
views
Prove that a language is not regular with process of elimination [duplicate]
When deterministic automaton, I need to prove that you can't implement the language in it, because the language is not regular.
Easiest way to prove that a language is regular, is just by making an ...
1
vote
1
answer
342
views
Is it Regular Language?
According to Wikipedia, Regular Language is Recognized by Some DFAs, or expressed by Regular Expression .. and all finite Language are regular but, not all regular is finite ..
that's mean it may be ...
1
vote
1
answer
616
views
Show that a regular language L contains only palindromes if and only if all words of length at most 3n are palindromes
This is an extension of a previous question asked by a different user earlier:
Let $x, u, v, w, y, x', u', v', w', y'$ be words satisfying
$y'x' = xy$.
$y'u'x' = xuy$.
$y'v'x' = xvy$.
$y'w'x' = xwy$....
1
vote
1
answer
243
views
Don't understand closure under string reversal
I am trying to learn from http://www.cs.uiuc.edu/class/su08/cs273/lectures/lect_06.pdf #2 and I understand everything except for the 2nd line of delta prime prime function,
I having breaking down ...
1
vote
1
answer
4k
views
Show that the regular languages are closed against taking "the second half" [duplicate]
Given $L$ is regular, the proof that $\mathrm{HALF}(L)$ is regular is pretty straightforward to me (e.g., #11 in this link): simply making a NFA and meeting in the middle with 2 original DFAs, the ...
1
vote
1
answer
3k
views
Decidability of an regular expression
I have this question about if the decidability of an regular expression and would appreciate if someone can check my answer and see if it makes sense, and if not, what is missing.
Be A = {(R)|R it ...
1
vote
2
answers
348
views
Is this pumping lemma proof correct?
$$ L = \{a^ib^jc^k \mid i,j,k > 0 \text{ and } i+k>j\} $$
I say it's not regular. Proof by pumping lemma:
Find a string $xy^iz$ that is not in $L$ (respecting the constraints).
Let $w=x^py^pz^p$...
1
vote
1
answer
3k
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 ...
1
vote
1
answer
541
views
A regular expression for a given formal language
I wanted to ask if someone can help me to construct a regular expression over the alphabet $\{a,b,x\}$ for the language $L$ which is constituted by all strings containing an odd number of $a$'s, and ...
1
vote
1
answer
58
views
Does a language dictate the order of the word?
Lets take the Language $$L = \{ (ab)^na^k | n \ge k \}$$
Does it dictate, that the $(ab)^n$ comes before the $a^k$ ? Or is the order irrelevant as long as it matches the $n \ge k$ criterium?
In simple ...
1
vote
1
answer
81
views
Is (a*b) or (a*b)* star-free?
Here is the proof of a∗ being star-free:
$\Sigma* = \bar{\emptyset} $
$ A∗= \overline{Σ∗(Σ∖A)Σ∗} $
Would this be a proof for $a * b$? :
$ A∗B= \overline{Σ∗(Σ∖A)Σ∗(Σ∖B)} $
For $(A * B )*$ it seems more ...
1
vote
1
answer
52
views
Prove $\{a^kb^l: 1\leq k\leq l\}$ is not regular using Myhill-Nerode theorem
I have searched quite a few posts here so that I can prove that the language $$L=\{a^kb^l: 1\leq k\leq l\}$$ is not regular (using Myhill-Nerode's theorem). I know that I must find an infinite number ...
1
vote
1
answer
40
views
Counting States in the trim automaton for $\cup_{i=1}^{p} L_i \circ L'_i$
Preliminaries. Let $n,m,i,j,p,c \in \mathbb{N}$ with $n,m,i,j,p,c \geq 1$.
Let our alphabet be $\{0,1\}$, with
non-empty languages $ L_i \subseteq \Sigma^n$ and $ L'_i \subseteq \Sigma^m$.
The other ...
1
vote
1
answer
103
views
Check if these 2 regular expressions are equivalent
Check if these 2 regular expressions are equivalent:
$R_1 = (a+b)^*(aa+bb)$
$R_2 = (a+b)^*aa+a^*bb+b^+b$
My approach:
We check if both of these expressions generate the same set of strings. Meaning ...
1
vote
1
answer
101
views
Transform a non-regular language into a regular one using sort
Is there a way where sort turns a non regular language into a regular one.
What I mean by sort is this:
Consider the language $L =$ { $bac, cbca, acbb$}. $sort(L) = $ {$abc, abcc, abbc$} respectively.
...
1
vote
1
answer
142
views
Regularity or non-regularity of union of two languages
Consider this language:
$K=\{xy \mid x=\{a,b\}^*, y=x^R \text{ or } y=x\}$
I know that these languages are non-regular separately:
$K_1=\{xy \mid x=\{a,b\}^*, y=x^R\}$
$K_2=\{xy \mid x=\{a,b\}^*, y=x\}...
1
vote
1
answer
36
views
Is it true that $R.L^* + L^* = R + L^*$?
I am trying to solve a problem to show equivalence between two regular expressions, and simplifying one of them I got $R.L^* + L^*$ in the end which I am not sure how to simplify further.
I want to ...
1
vote
1
answer
192
views
How to design a DFA that accepts the language of pairs of binary words (a,b) with 5a=b?
Let $\begin{bmatrix}0\\ 0\end{bmatrix}$ be a two-column vector with $0$ in the first row and $0$ in the second row.
Let $\Sigma_2 = \left\{
\begin{bmatrix}0\\ 0\end{bmatrix},
\begin{bmatrix}0\\ 1\end{...
1
vote
1
answer
124
views
Is the equivalence problem of a CFG and a FSM decidable?
I have the following problem:
Given a context-free grammar $\mathcal{G}$ and a finite state automaton $\mathcal{A}$, where both are over the alphabet $\Sigma=\{0, 1\}$. Is it decidable whether $L(\...
1
vote
1
answer
222
views
Check whether a regular expression is correct
I'm given a description of a regular language $L$, and I have a candidate regular expression $R$. Is there a systematic, step-by-step way to test whether the candidate regular expression is correct?
...
1
vote
1
answer
130
views
Shuffle of a DCFL and a regular language
This is problem 88 from Miscellaneous exercises of Kozen's "Automata and Computability".
The shuffle $A||B$ of two languages $A$ and $B$ is defined as $\{w \mid w = a_1b_1\ldots a_kb_k,$ ...
1
vote
1
answer
79
views
Regular Language to Regular Expression
Let's assume I have the following regular language:
L = {1,0}*{010}{1,0}*
I would like to convert this to regex for a program. Would the equivalent regular expression for this be:
((0+1)*(010)(0+1)*)
...
1
vote
1
answer
82
views
State Complexity of DFAs for Restricted Languages
Let $\Sigma$ be a finite alphabet. All strings below are over $\Sigma$.
Definitions:
If a string $s = vw$, then $v$ is a $\textit{prefix}$ of $s$ and $w$ is a $\textit{suffix}$ of $s$.
For a language $...
1
vote
1
answer
86
views
Myhill-Nerode equivalence under a function
Consider two finite languages, $L_A$ and $L_B$, potentially over different alphabets. Now since these languages are finite, there exist minimal acyclic deterministic finite-state automata to decide ...
1
vote
1
answer
251
views
How are regular languages not structurally recursive?
This blog posting states that "regular languages aren't structurally recursive" while
"That's not the case for context-free grammars"
In what sense is the term "structurally ...
1
vote
1
answer
64
views
If $L$ is regular then $\{x~|~\exists y ~~s.t~~ xyx^R \in L\}$ is regular
Prove/disprove the following claim:
If $L\in RL$ then $\{x~|~\exists y ~~s.t~~ xyx^R \in L\} \in RL$
I think that this is true, and my intuition is by using $L_{pq}$ s.t:
For every $(p,q)\in Q\times Q$...
1
vote
1
answer
168
views
Prove that the language of regular expressions is not regular
I want to prove that the language of all regular expressions is not a regular language. I'm having trouble to approach this problem. I thought maybe to show that the parenthesis language is a part of ...
1
vote
1
answer
3k
views
Why L1 := { a^n b^m | m, n ≥ 0 and m ≥ n } is regular and L2 := { a ^ n b ^ n | n>= 0 } not regular?
I understand why L2 is not a regular language. We can use the pumping lemma to prove it
In the case of L2:
assume n = 1 and string = ab
We assume that L2 is regular, so it has "pumping length&...
1
vote
1
answer
46
views
Problem with Understanding Pumping Lemma
I'm trying to solve this exercise that asks to determine whether a language is regular or not.
Following the flow of the course I figured that the exercise is a test for Pumping Lemma application. But ...
1
vote
2
answers
164
views
Empty string in an ambiguous grammar?
I'm a bit confused by the role of the empty string in this ambiguous grammar:
A' -> A
A -> if A B
A -> null
B -> [empty string]
B -> else S
So what ...
1
vote
1
answer
187
views
Dividing a String According to the Pumping Lemma
I have some questions about how a string can be divided into pieces according to the pumping lemma. I am learning from Michael Sipser’s book Introduction to the Theory of Computation, 3rd Edition. He ...
1
vote
1
answer
343
views
Correct complement of a regular language when the union of the languages do not lead to entire set of strings over the given alphabet?
I have a question that says that the complement of a regular language given as:
$L_1=\{a^nb^m|(n+m)<5\}$ is $L_2=\{a^nb^m|(n+m)\geq5\}$ over $\Sigma=\{a,b\}$, and therefore, we can simply construct ...
1
vote
1
answer
127
views
Is $(L_1^c \cup L_2^c)^c$ context-free or context-sensitive
I came across the following question:
Let $L_1$ be a regular language and $L_2$ be a context-free language. Let $L_1^c$ and $L_2^c$ be their complements respectively. What can be said about $(L_1^c \...
1
vote
1
answer
63
views
Using pumping lemma to prove that $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $ is irregular
Given the following language:
$L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $
I am trying to prove that it is not regular. On the one hand my intuition tells me that the language is non-regular as ...
1
vote
1
answer
145
views
Proof regular languages are closed under homeomorphism
Let $\Sigma_1 , \Sigma_2$ be alphabets. Let $L\subseteq \Sigma_1^*$ be a regular language, and let $ h:\Sigma_1^* \rightarrow \Sigma_2^* $ be a homomorphism.
Proof $h(L)$ is regular.
I have written a ...
1
vote
1
answer
513
views
Proving a language with $(ab)^n$ is not regular with pumping lemma?
I have been working to understand the pumping lemma better, but I am quite stuck at proving these two languages is not regular:
\begin{align}
L_1 &= \{(ab)^n c^m \mid n\ge 1, m\ge 2n \} \\
L_2 &...