Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,761
questions
2
votes
0
answers
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 ...
- 181
-2
votes
1
answer
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?
- 11
0
votes
1
answer
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
0
votes
1
answer
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 ...
0
votes
1
answer
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).
0
votes
2
answers
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 ...
- 197
3
votes
2
answers
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:
...
- 33
0
votes
1
answer
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 ...
-1
votes
2
answers
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 ...
- 1
0
votes
0
answers
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 ...
- 1
4
votes
0
answers
147
views
Regular languages for which star height is not increased by complementation
The set of (non-generalized) regular expressions over an alphabet $\Sigma$ is the set of expressions generated by the following grammar, where $a\in \Sigma$ ranges over symbols in the alphabet:
$$
\pi ...
- 41
0
votes
0
answers
27
views
If string x is conjugate to string y, how can you prove that the reverse of x is conjugate to the reverse of y?
I am relatively new to writing proofs and I am stuck trying to prove that if $x$ ~ $y$, then $x^R$ ~ $y^R$. Any help would be appreciated!
1
vote
0
answers
81
views
Regular Languages are closed under Scarne's Cut
This exercise come from Sipser (1.68).
In essence, show that if $A$ is regular, then $CUT(A) := \{yxz | xyz \in A\}$ is regular. I've managed to show that $B = \{yx | xyz \in A\}$ is regular. ...
- 111
1
vote
0
answers
16
views
Contiguous-substring operator
If string concatenation $ab$ is like left- and right-multiplication, is there any infix (latex) operator notation I can use for checking for contiguous substrings, like $bc \subseteq abcd$? $\subseteq$...
- 11
0
votes
1
answer
534
views
Show that if L is CFL and R is a regular language then {w ∈ Σ^∗ | xw ∈ L for some x ∈ R} is context free
Show that if $L$ is CFL and $R$ is a regular language such that they both share the same input alphabet $\Sigma$, then $C = \{w \in \Sigma^*\mid xw \in L$ for some $x \in R\}$ is context free.
Hi I'...
5
votes
1
answer
123
views
$\{uuv\mid u\in\Sigma^+, v\in \Sigma^*\}$ and pumping lemma
As I am currently teaching regular languages and pumping lemma, I was searching for nice examples of languages, regular or not, for exercises.
$L_1 = \{vv\mid v\in \Sigma^*\}$ is a classic example, ...
- 12k
1
vote
1
answer
161
views
Describing the language of this Automaton
I am trying to describe the above automaton in English. The pattern that I can see is that it accepts any input that starts with $1$ or $0$ with an exact one occurrence of $00$ and ends with 1 or 10. ...
- 111
1
vote
2
answers
46
views
Which z should I pick?
I'm currently trying to show that the language $L_2=\{0^n \text{ } | \text{ } n=2^k, k\geq 0\}$ is not regular by using the Pumping Lemma (at least I think it is not regular, because I couldn't find ...
- 225
1
vote
1
answer
49
views
Proving irregularity of $a^{k!}$ using Nerode's theorem
Use Nerode's theorem to prove that the following language $L$ is not regular:
$$ L=\{a^{k!} \mid 1\leq k\} $$
Here is my attempt:
Let $A$ be an infinte set of words s.t- $$ A=\{a^n \mid n\in \mathbb{...
- 135
1
vote
1
answer
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 ...
- 225
0
votes
1
answer
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....
user146045
-1
votes
1
answer
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?
- 11
0
votes
1
answer
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$...
user145974
0
votes
1
answer
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 ...
user145509
1
vote
2
answers
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 ...
- 19
0
votes
1
answer
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 &...
- 1
2
votes
1
answer
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 ...
0
votes
1
answer
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 ...
- 101
0
votes
1
answer
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 ...
0
votes
3
answers
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{
...
- 111
2
votes
2
answers
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 ...
- 47
0
votes
1
answer
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 ...
- 9
0
votes
2
answers
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 ...
- 33
3
votes
2
answers
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.
- 31
0
votes
1
answer
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
1
answer
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 ...
- 33
2
votes
0
answers
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 ...
- 33
0
votes
1
answer
70
views
Need help with constructing a DFA
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 ...
- 465
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)...
- 21
-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 ...
- 1
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 $0$s and $1$s in the string $x$ respectively. Consider the following two ...
- 3
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 ...
- 255
-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$. ...
- 113
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 ...
- 303
1
vote
1
answer
47
views
Regular expression for all a* except aa?
I'm stumped on how you would describe a language which is a* except for aa, so the following is acceptable:
a
aaa
aaaa
aaaaa
...
It's for part of the below DFA
- 111
0
votes
2
answers
427
views
Regularity of CFG and DCFL
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 ...
- 315