As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [regular-languages]

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

1,761 questions
Filter by
Sorted by
Tagged with
62 views

### Translating weighted regular expressions with the complement operator to weighted deterministic automata

I want to implement regexp search via translation to deterministic automata, as a toy project. TLDR: how to combine the extended regular expressions with the weighted regular expressions, with the ...
167 views

### Is this language regular or non-regular : {ww | w ∈ {a,b}* } ∩ {a}*

I think it's a regular language but I can't find a DFA or a regular expression. Would anyone know how to help me?
295 views

### Intersection between CSL and CFL?

I am trying to find a proof of A ∩ B where A is a CSL and B is a CFL. Also I know that CFL is a strict subset of CSL. Does that mean that their intersection will give CFL. I am stuck
83 views

### Intersection of Infinite Regular Language with CFL

Intersection of any finite regular language with anything( CFL or not CFL) will be finite but what about intersection of infinite regular language with CFL or not CFL. Does the resultant will be ...
368 views

### How to prove that regular languages are closed under reversal, inductively?

There are some threads that discuss it but I haven't came across an inductive one yet. All of them involve creating a finite automaton which I would like to avoid (as per my professors requests).
327 views

### For a regular language L, the language of all words such that no prefix of them are in L is also regular

Prove that for every regular language $L$, the following language is regular: $L_{pf}=$ $\{x \in L |$ no proper prefix of $x$ is in $L\}$ How should I prove this? I understood that $L_{pf}$ is just ...
252 views

### LALR(1) grammar for simple math parser

I am trying to write a simple parser for a small calculator project, that should be able to parse e.g. the following inputs: ...
70 views

### Decidability of a given grammar if it is regular

According to my course the question "Is $L(G)$ regular?" undecidable. But I was more interested in knowing the exact algorithm or proof that makes this question undecidable. To further ...
366 views

### Convert ((ba ∪ ab)∗ ∪ b)* to NFA

How do I simplify this $((ba \cup ab)^∗ \cup b)^*$? I can draw the NFA for the '$ba$', '$ab$' and '$b$' term but when it comes to linking the '$ba \cup ab$' to the '$)^∗ \cup b)^*$' i am unsure how ...
24 views

### How ot prove a language is regular using L′ = {ab(^i)c)^i) | i ≥ 0 [duplicate]

I have the following language L = {a(^i)b(^j)c(^k) | i, j, k ≥ 0, and, if i = 1 then j = k} . How do I use the fact that L′ = {ab(^i)c)^i) | i ≥ 0 to prove that is it not regular? I am given a hint ...
147 views

1 vote
43 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 ...
68 views

### I want to determine if this language is non regular-any tips?

After working through some examples of proving the non-regularity of languages I encountered this language $$L = \{(ab)^{i}a^{j} | i \geq j, i,j \in \mathbb{N}\}$$ Where $a^{k}$ = a repeated k times.... 79 views

### Is the right quotient of a regular language respect to another regular language a regular language?

Will the language $\{w\in L_1\mid \exists v, wv\in L_2\}$ be regular if $L_1$ and $L_2$ regular languages?
139 views

### How to design PDA for this language?

I'm having a hard time trying to build the PDA for this language: $$L=\{a^nb^m: n,m \geq 1 \land m=4n+2\}$$ I don't know how many $a's$ should I push into the stack when reading $a$, and how many $a's$... 70 views

### Is the language $L=\{a^nb^m:n,m\in\mathbb{N}\land n-m=5 \}$ regular or not regular?

I'm trying to understand how to prove a language is regular or not regular, for example this language: $$L=\{a^nb^m:n,m\in\mathbb{N}\land n-m=5 \}$$ Is this language regular or not? My solution Using ... 1 vote
310 views

### Let Σ = {a} be a one-element alphabet and L ⊆ Σ^* be an arbitrary language over Σ = {a}. Show that L^* is regular [duplicate]

I have a computer science question: Let Σ = {a} be a one-element alphabet and L ⊆ Σ^* be an arbitrary language over Σ = {a}. Show that L^* is regular These are all the facts I have been able to gather ...
190 views

### Can any language be expressed by regular expression?

I'm studying Autoamta Theory currently and am wondering if any Language (for example Lanugage L in Alphabet A={a,b}) can be expressed by regular expression. In my current understanding the rule is &...
229 views

### Proving that a specific Turing machine accepts a regular language

Calling all math buffs! ;) A Turing machine has two states - one accepting and one non-accepting. Furthermore, the Turing machine cannot overwrite blank symbols. (Note: It's assumed that the blank ...
120 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 ...
192 views

### Can a non-regular language have a regular grammar?

Basically the title. I am supposed to find a regular grammar for the language that produces palindromes. This is all I have right now: S -> 1 | 0 | ε Since it ...
298 views

### Can the diagonal language be empty?

We defined the diagonal language as follows in the lecture: \begin{align*} L_{\text{diag}}=\left\{w \in \left\{0, 1\right\} ^{*}\mid w=w_{i} \text{ for some }i \in \mathbb{N} \text{ and }M_{i} \text{ ...
336 views

### Understanding the application of the pumping lemma to show that $L=\{0^{2^p}, p \geq 0\}$ is not regular

I want to understand how is this proof working. What I know: Pumping lemma for regular language-: Let $L$ be regular language. Then there exists a constant $n$ which depends on $L$ such that for every ...
1k views

### Regular expression for set of all strings containing no 3 consecutive 0s?

The answer is $1^*01^*01^*+1^*(0+00+\in)1^*$ If I had to rephrase my question, it would be how to approach regular expression problems? Is it all about practice? How do I understand what the regular ...
202 views

### Check Proof Using Pumping Lemma to Show Language Not Regular

Please check my proof where I use the pumping lemma to show that the language $B=\{0^n1^n | n≥0\}$ is not regular. I'll state the pumping lemma here for clarity: Pumping lemma If $A$ is a regular ...
1k views

### Regular Expressions - What is difference between a+ and a⁺

I'm very confused as to if a+ and a⁺ mean the same thing or are completely different.
157 views

### Prove that $\{xyz \mid zyx \in A \}$ is regular if $A$ is regular

Does the following work and is there anything possibly simpler? Let $X = (Q, \Sigma, \delta, s, F)$ be a DFA for $A$. Intuitively, we want to "remember" (or guess) two states $p$ and $q$ ...
1 vote
101 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 ...
51 views

### Summary of Pumping Lemma Application

For my own understanding I would like to summarize how to use the pumping lemma to show that a language is not regular. The pumping lemma is defined as follows. Pumping lemma If $A$ is a regular ...
70 views

I am trying to construct the DFA that accepts the following language $$L_2 := \left\{ w \in \{a,b\}^* \mid \#a(w) \text{ is divisible by } 3 \text{ and } \texttt{babbab} \text{is a substring of } w \... 3 votes 2 answers 54 views ### How to show closure of regular languages without DFA,NFA,reg expressions Given a \Sigma I define a regular language as one of the folllows: \emptyset \left\{ \sigma \right\} for any \sigma \in \Sigma L_1 \cup L_2 for regular L_1, L_2 L_1 \cdot L_2  for ... 2 votes 1 answer 56 views ### The Closure Of Regular Language Under Reordering Alphabets For a regular language A with the alphabet \{a, b\}. Is L a regular language, where L contains strings of A but sorted with a and b? In other words, formula: L = \{ a^{\#_a(x)}b^{\#_b(x)... -2 votes 2 answers 671 views ### Prove that the class of regular languages is closed under three operation We define an operation three on strings as three(c1c2c3c4c5c6...) = c3c6... then the above-described definition is extended to languages. Prove that the class of regular languages is closed under this ... 0 votes 1 answer 217 views ### Prove the class of regular languages is closed or not closed under the operations below Suppose A and B are both languages over \Sigma=\{0,1\}. We use n_0(x) and n_1(x) to represent the number of 0s and 1s in the string x respectively. Consider the following two ... 0 votes 1 answer 268 views ### Size of minimal DFA Assume a given NFA for a regular language with n states. It is clear that determinizing it may result in an DFA with \Omega(2^n) states. However, the minimization might decrease the number of ... -1 votes 1 answer 544 views ### Show that {xy : x,y ∈ {a,b}*, |x| = |y|, x ≠ y} is a not a regular language Actually, I know that there are many examples showing how this is a contex-free language, but I can't find any that show it isn't regular. I would appreciate if I could have a solution step by step ... 1 vote 2 answers 310 views ### What is the minimum pumping lemma length of 01^*0^*1? I've taken the following steps to prove that the minimum pumping length (PL) of the above language, L= 01^*0^*1: Set a PL. I chose p=2 Choose a string from L where |w|\geq p, I chose w=011. ... 0 votes 2 answers 126 views ### Show that \{xy : x \in \{a\}^*, y \in \{b\}^*, |x| = |y|\} is a not a regular language I have been asked as an exercise how to prove that this is not a regular language. first I tried to use the pumping lemma, but I got stucked. Th erxercise hust said to prove thata this isn't a regular ... 0 votes 0 answers 61 views ### If L is regular, is L/w = \{x\mid wx\in L\} regular? I'm trying to see if the language L/w = \{x\mid wx\in L\} is regular given that L itself is regular. It seems to me that if L=L(A) for the NFA A = (Q, \Sigma, \delta, S, F), then the NFA A' ... 2 votes 2 answers 65 views ### If L is regular so is the language of compressed doubles Suppose L is a regular language over the alphabet \Sigma. I need to prove that$$ L'=\{x_0\cdots x_n:x_0x_0x_1x_1\cdots x_nx_n\in L, \ \ x_i\in \Sigma\} I thought I could take a DFA which computes ...
1 vote
I read that it is undecidable whether, given a CFG $G$, $L(G)$ is regular. And there exists no algorithm that, given a CFG $G$ such that $L(G)$ is regular, outputs a DFA that accepts $L(G)$. My ...