Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
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 *) ...
beoliver's user avatar
  • 113
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 ...
maqo's user avatar
  • 147
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 (...
Dumb Scientist's user avatar
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$...
Luz's user avatar
  • 343
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 ...
Liana's user avatar
  • 43
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 ...
marka_17's user avatar
  • 125
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?
sir_thursday's user avatar
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 ...
TheoryQuest1's user avatar
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{...
Darkflame's user avatar
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 ...
St.Antario's user avatar
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 ...
user1868607's user avatar
  • 2,194
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 ...
bandit_king28's user avatar
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?
user270494's user avatar
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 ...
Victor Brunell's user avatar
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 ...
Ben Beri's user avatar
  • 115
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 ...
Yassine's user avatar
  • 135
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$....
David Smith's user avatar
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 ...
QIANG's user avatar
  • 51
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 ...
QIANG's user avatar
  • 51
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 ...
user2752471's user avatar
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$...
redundant6939's user avatar
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 ...
Iancovici's user avatar
  • 665
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 ...
forrestGump's user avatar
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 ...
Robert's user avatar
  • 57
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 ...
Crea Teeth's user avatar
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 ...
Νικολέτα Σεβαστού's user avatar
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 ...
ShyPerson's user avatar
  • 925
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 ...
RandomGuyOnMath's user avatar
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. ...
Anonymous's user avatar
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\}...
Birborian's user avatar
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 ...
Axo's user avatar
  • 115
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{...
Patrick's user avatar
  • 11
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(\...
sockaddr's user avatar
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? ...
D.W.'s user avatar
  • 159k
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,$ ...
ayan's user avatar
  • 13
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)*) ...
Bradley Lund's user avatar
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 $...
ShyPerson's user avatar
  • 925
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 ...
ShyPerson's user avatar
  • 925
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 ...
user3414663's user avatar
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$...
Math4me's user avatar
  • 249
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 ...
user150587's user avatar
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&...
Pratik Hadawale's user avatar
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 ...
Tita's user avatar
  • 225
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 ...
Shisui's user avatar
  • 121
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 ...
billiam's user avatar
  • 33
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 ...
Userhanu's user avatar
  • 137
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 \...
shantanu4raje's user avatar
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 ...
jaime martinez's user avatar
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 ...
SaharCo's user avatar
  • 43
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 &...
mhanxsolo's user avatar

1
18 19
20
21 22
37