Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,607
questions
0
votes
0answers
15 views
A regular expression E* defines an infinite language $L_E$ [closed]
So I'm studying for an exam which is about languages and automata. There is a question in the book which asks us to prove that given a regular expression that can be infinite, say $E*$, the language ...
-1
votes
0answers
16 views
Describe how to build a non-deterministic Turing machine that accepts the set of all element prefixes of $L$, i.e, $PREFIX(L)$
Describe how to build a non-deterministic Turing machine that accepts the set of all element prefixes of $L$, i.e, $PREFIX(L)$.
Hello, I have been trying to solve this problem, my intuition tells that ...
1
vote
0answers
8 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$...
0
votes
1answer
33 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'...
4
votes
1answer
62 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, ...
1
vote
1answer
47 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. ...
0
votes
0answers
16 views
Could I have used PL directly on this language instead of proving it the way I did? [duplicate]
In an exercise I'm trying to solve I have to say whether a language is regular or not. One of the languages is $L_1=\{0^i1^j \mid i,j \geq 1\text{ and } i\neq j\}$.
I have already solved this by ...
0
votes
1answer
25 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 ...
1
vote
1answer
35 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{...
1
vote
1answer
31 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 ...
0
votes
0answers
26 views
PDAs with bounded stacks accept regular languages [duplicate]
I've been trying to solve the following problem from Martin's Introduction to languages and the theory of computation, 4th edition:
Suppose that $L \subset \Sigma^{*}$ is accepted by a PDA $M$. ...
0
votes
1answer
57 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....
-1
votes
1answer
47 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?
0
votes
1answer
47 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$...
1
vote
0answers
60 views
Is there a complexity measure on regular grammars connected to the descriptional complexity of the DFAs?
This question is directed at DFAs/NFAs and regular languages and regular grammars.
Define the "descriptional complexity" of a language as the size complexity of the family of DFAs that ...
0
votes
1answer
42 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
2answers
46 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 ...
0
votes
1answer
33 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 &...
2
votes
0answers
132 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
1answer
26 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 ...
0
votes
1answer
22 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
3answers
234 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{
...
1
vote
1answer
43 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 ...
0
votes
1answer
33 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 ...
0
votes
2answers
54 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 ...
3
votes
2answers
578 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.
0
votes
1answer
51 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
1answer
50 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 ...
2
votes
0answers
34 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 ...
0
votes
1answer
46 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 \...
1
vote
1answer
22 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 ...
1
vote
1answer
37 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
2answers
76 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
1answer
46 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 ...
0
votes
1answer
56 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
1answer
69 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
2answers
43 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
2answers
77 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
0answers
58 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
2answers
58 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
1answer
26 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
0
votes
0answers
55 views
Whether $L(G)=L(R)$ is decidable for DCFL and CFL?
Let $G_1$ be the context free grammar and $R$ be regular language. Now I have to check whether $L(G_1)=L(R)$ is decidable or not?
My approach $\overline{L(G_1)}=\overline{L(R)}$. Now $L(G_1)$ not ...
0
votes
2answers
163 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 ...
1
vote
1answer
70 views
Why equality is decidable for regular language but not for $CFL?$
There are infinitely many different $PDAs$ for the same $CFL$ exist, therefore we can't check equality for $CFL.$
But also there are infinitely many different $DFA$ exists for same regular language. ...
0
votes
1answer
48 views
Is set of all RE languages $\subseteq\\$ $\Sigma^{*}?$ [closed]
We know that any languages $\subseteq\\\\$ $\Sigma^{*}.$ Because any language collection of string over alphabet. And we know that set of all languages is $2^{\Sigma^{*}}$ which doesn't $\subsetneq\\\\...
1
vote
1answer
144 views
Adding a finite set to a non-regular language
Suppose $A = \{0^{n}1^{n} \mid n \ge0\}$, which is not regular, and let $B$ be a finite subset of $\Sigma^* \setminus A$. Is $A \cup B$ regular?
1
vote
1answer
52 views
Difference between (0)* and (0*)*
I know that,
0* generates, NULL, 0, 00, 000, 0000, ... and so on.
But how does (0*)* ...
0
votes
1answer
53 views
How to convert this regular grammar into a finite state automaton?
In a French course (p. 13) there is a language of words of {a,b,c} containing at least one occurrence of the string bac.
The ...
1
vote
1answer
23 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
2answers
51 views
Irregularity of $\{a^p : p \text{ prime}\}$ using Myhill–Nerode
Consider the language
$$ L = \{2^k : k \text{ is prime}\}. $$
This language contains, for example, $2^3=222$, $2^5=22222$, $2^7=2222222$, and so on.
I know that $L$ is irregular and so there must ...
