Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,684
questions
0
votes
1
answer
43
views
DFA and NFA with 2 Substrings
I am preparing for my CS exam and found this question in a collection of old exams:
Find a DFA and NFA with Σ = {o,p,q} that checks if the substrings op and pq are present in the string.
I thought, ...
- 113
3
votes
1
answer
70
views
Exotic closure of regular languages
Let $L_1 \subseteq \{0,1\}^{*}$ be a regular language, and let $L_2 \subseteq \{0,1\}^{*}$ be some (not necessarily regular) language.
Show that
$$L=\left\{ \sigma_{1}\#\sigma_{2}\dots\#\sigma_{n}\mid\...
- 161
-2
votes
0
answers
23
views
How to use Pumping Lemma $L = { wsw | w ∈ {0,1}*, s ∈ {2}*, and |w| = 2 * |s| }$?
I'm trying to use the Pumping Lemma to prove that $L = { wsw | w ∈ {0,1}*, s ∈ {2}*, and |w| = 2 * |s| }$ is not a CFL.
-2
votes
0
answers
27
views
How to use Pumping Lemma for L={www|w∈{0,1}* and w starts with 0}?
I know my question might be a bit similar to How to use Pumping Lemma for $L = \{www | w∈\{0,1\}^*\}$
However, I feel that it is different enough due to the extra requirement of starting with 0
1
vote
1
answer
67
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 ...
- 111
-2
votes
1
answer
42
views
Why is $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ a regular language?
Define $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ while $\#\notin \Sigma$
Why is $L'$ a regular language?
I have tried to construct the DFA of L, then with a # move to a copy of this DFA with flipped ...
- 241
0
votes
0
answers
15
views
Regular, CFL, non-CFL infinite closures [duplicate]
I was wondering about infinite closure properties.
Are the Regular languages closed under infinite union? Infinite intersection?
Probably not, by taking $\forall n>0~~L_n=\{a^nb^n\}\in RL$, then $\...
- 241
3
votes
4
answers
2k
views
Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?
Why is $L=\{w \mid ~|w|\bmod3=\#_a(w)\bmod3\}$ a regular language?
$\#_a(w)$ is the number of $a$'s in $w$.
So far every language that I saw containing modulo was a ...
- 241
0
votes
0
answers
29
views
How to show that $\{a^p ~|~ p\text{ is not prime}\}$ is not a CFL? [duplicate]
I want to show that the language $L=\{a^p ~|~ p\text{ is not prime}\}$ is not a CFL.
If I look at $\bar{L}=\{a^p ~|~ p\text{ is prime}\}$, it is pretty straightforward to show that it is not a CFL ...
- 241
4
votes
0
answers
68
views
Regular language superset with exactly exponential size
Definitions
Define the density $\rho_L$ of a language $L$ to be a function $\rho_L : \mathbb{N} \rightarrow \mathbb{N}$ where $\rho_L(n)$ is the number of words in $L$ of length $n$.
Question
Let $L \...
- 186
2
votes
1
answer
36
views
Why is $L=\{w~|~\#_a(w) \ge \#_b(w)\}○\{w~|~\#_a(w) \le \#_b(w)\}$ regular?
Why is this language regular: $L=\{w~|~\#_a(w) \ge \#_b(w)\}○\{w~|~\#_a(w) \le \#_b(w)\}$?
Where $\#_a(w)$ is defined as the number of $a$ in $w$.
Isn't that a concatenation between 2 CFL?
Thanks!
- 241
0
votes
0
answers
37
views
If two states of a DFA are k-equivalent and k+1 equivalent
Let $p,q$ be two states of a DFA, such that $p\equiv_kq$ and $p\equiv_{k+1}q$.
Does it mean that $p\equiv q$ ?
I don't think so, because if the minimization algorithm can continue, they might be ...
- 241
0
votes
1
answer
48
views
Prove or disprove that $\{xc o(x) :x \in A\}$ is context-free, where A is a regular language
Suppose o is a map on strings to strings. For every language R, we let $o(R) := \{o(x) : x \in R\}$. If o(R) is a regular language for every regular language R, then prove or disprove that the ...
- 225
1
vote
1
answer
40
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$...
- 241
1
vote
3
answers
175
views
How to prove that $half(L)=\{x|xy\in L,|x|=|y|\}$ is Regular Language
Let $L$ be a regular language.
Define: $half(L)=\{x|xy\in L,|x|=|y|\}$
Prove that $half(L)$ is regular as well.
I have seen a hard proof by using the DFA A of L, building a NFA B (such that every ...
- 241
0
votes
2
answers
83
views
CFL with regular substitution to make a regular language
If I have a CFL, can I define a regular substitution to make it a RL?
For example, if I have the language $\{a^nb^n \mid n\ge0\}:$
Define $h(a)=a$ , $h(b)=b$, then $h(L)={a^*}$ , am I right?
Thanks!
- 1
3
votes
1
answer
81
views
Decide whether regular language contains a word $w$ for which $|w| = n^2$
Task:
Input: DFA $M = (Z, Σ, δ, q_S, E)$
$T(M)$ := Language that $M$ accepts.
Question: Does $T(M)$ contain at least one word $w$ such that $|w| = n^2$ with $n \in \mathbb{N}$$ ?$
My attempt:
Since ...
0
votes
1
answer
57
views
How would I design a State Diagram (FSM) for a AC unit?
Ok so I'm learning Finite Automata in my Theory of Computation course and understand the basic FSM but can't wrap my head around this question:
The AC should only turn on if a person is
detected in ...
1
vote
1
answer
40
views
Is the given language regular, CFL or in P
someone sent me a question lately and I wasn't able to solve it so I'm asking for help.
Question: Given the language
$$L=\{w\in\{0,1\}^*:|w| \text{ is even and the first half of it has a balanced ...
- 456
0
votes
1
answer
51
views
CFG to RG Conversion
I'm struggling with this question. I would appreciate a detailed solution as it would help me better understand the subject.
Convert the following Context Free grammar into a Regular Grammar:
S -> ...
-1
votes
1
answer
80
views
Decidability of intersection of regular and decidable languages
I'm wondering if a language (A) is a decidable language and language (B) is a regular language, is the intersection between A and B regular?
- 1
-1
votes
1
answer
36
views
determining the relationship between two regular languages using the myhill nerode theorem
For a regular language $A$ with an alphabet $\Sigma$, define an equivalence relation for strings $x,y \in \Sigma^*$ by $x\equiv_A y\Leftrightarrow \,\forall w\in \Sigma^*, xw, yw\in A$ or $xw, yw\not\...
- 225
0
votes
2
answers
28
views
How to prove non-regularity with Myhill-Nerode theorem?
I have a problem in proving of nonregularity of EQ_n = {u = v2v : |v| = n}. I just dont know how to start. Can you help me?
- 11
5
votes
1
answer
173
views
Is the set of languages satisfying the pumping lemma closed under concatenation?
Let $L$ be the set of all languages that satisfy the pumping lemma, including non-regular languages that satisfy it. Is the set $L$ closed under concatenation?
I couldn’t prove it or find a ...
1
vote
1
answer
62
views
How to convert AFA to ε-NFA / NFA / DFA?
Alternating Finite Automata is a superset of NFA while being equal in expressive power to NFAs. It is defined by 6-tuple (Q∃, Q∀, Σ, δ, Q0, F) where all outgoing transitions from Q∃ are 'or'ed and ...
2
votes
1
answer
69
views
prove that if L is context-free then L' = {w2#w1 | w1#w2∈L} is context-free
Given that $\#\notin \Sigma$ and $L\subseteq \Sigma^*\#\Sigma^*$, prove that if $L$ is context-free language then $L' = \{w_2\#w_1 \mid w_1\#w_2\in L\}$ is context-free.
I'm trying to prove this in ...
- 21
5
votes
3
answers
102
views
If $L$ is regular then so is $\{y \mid \exists x \, xyx \in L\}$
For a language $\mathcal{L}$ over an alphabet $\Sigma$, define
$$\mathcal{SW(L)} := \{ y ∈ Σ^∗ \mid \exists x \in Σ^* \text{ such that } xyx \in \mathcal{L}\}$$
How can I prove that if $\mathcal{L}$ ...
1
vote
1
answer
77
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 ...
- 11
3
votes
2
answers
790
views
Determining if an NFA accepts an infinite language in polynomial time
Can we determine in polynomial time if the language accepted by an NFA is infinite?
The case of DFA is simple, but converting an NFA to a DFA may take exponential time.
Also, I ran into this post,
...
- 183
1
vote
1
answer
47
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&...
2
votes
4
answers
263
views
What exactly is pumping length in pumping lemma?
Pumping Lemma : For any regular language $\mathbb{L}$, there exists an integer $n$, such that for all $x\in \mathbb{L}$ with $|x|\geq n$, there exists $u, v, w \in \Sigma^*$, such that $x = uvw$, and
...
8
votes
1
answer
694
views
Conjecture: a half of a pairing context-free language must be a regular language
If $A$ and $B$ are languages, let $A\bowtie B$ denote the set of strings made by concatenating any word from $A$ and any word from $B$ of equal length.
$$A\bowtie B \equiv \{ ab : a\in A,\;b\in B, |a|=...
- 738
-2
votes
1
answer
31
views
How to cross verify the resultant E-NFA in "Regular Expression to E-NFA" is correct?
Let's say that we want to convert the regular expression: (ab + a)* to Finite Automata, where '+' is union and '*' is kleene star. Using the Thompson method, Thompson Method
I end up with this:
My ...
1
vote
1
answer
34
views
Converting Regular Expression to Finite Automata
I am studying "Theory of Computation" by Michael Sipser. I am studying the section where he teaches how to convert "RE to FA". He uses empty transitions for union, concat and star, ...
3
votes
0
answers
44
views
Are deterministic Büchi automata omega-closed?
As in, given a regular language $V$, does there exist a deterministic Büchi automaton $\mathcal{A}$, or equivalently a regular language $W$ such that $\mathcal{L}(\mathcal{A})=\vec{W}=V^\omega$?
For ...
- 141
2
votes
1
answer
39
views
Irregularity of $\{b^ma^n: (m,n)=1\}$ using Nerode [closed]
Let $L=\{b^ma^n \mid \text{$m$ and $n$ are coprime} \}$. Using Nerode's theorem, prove that $L$ is irregular.
From Nerode's theorem I know that $L$ is regular if and only if the number of equivalence ...
- 241
1
vote
2
answers
83
views
Construct a regular expression for the set of strings over {a, b} that contain an odd number of a's and at most four b's
Construct a regular expression for the set of strings over {a, b} that contain an odd number of a's and at most four b's.
So far, I have $(aa)^*a((b+\varepsilon)(aa)^*)^4$, but I don't think this ...
- 11
13
votes
4
answers
2k
views
Proving Equivalence of Two Regular Expressions
Consider the regular expressions
$(1+01)^*(0+\epsilon)$
$(1^*011^*)^*(0+\epsilon) + 1^*(0+\epsilon)$,
where $\epsilon$ is the empty string. I need to determine if these expressions are equivalent. ...
- 233
3
votes
3
answers
58
views
Can we choose different words for pumping Lemma to prove $a^n b^m:n\neq m$ is not regular?
$L=\{a^n b^m:n\neq m\}$
$L=\{a^n b^l c^k :k\neq n+l\} $
Can we take in case 1
$w=0^{2p}1^p$?
But my resource says that, we need to take
$w=0^{p}1^{p+p!}$
Similarly in case 2, I want to take
$w=a^p b^...
- 41
0
votes
0
answers
35
views
Prefix of regular language
we have the following languages - $L_1 ,L_2$ .
we'll define new language:
pref$(L_1,L_2)$= {x $\in$ $\Sigma$*| $\exists$ u $\in$ $L_2$ s.t: x $\bullet$ u $\in$ $L_1$ }
can we say that:
$L_1$ ,$L_2$ $...
3
votes
1
answer
39
views
Build an automaton from a given automaton to prove regularity of more complex strings
let $L$ be a regular language, and let $A=\{\Sigma, Q, q_0, F, \delta\}$ be a DFA such that $L = L(A)$.
I need to prove that $$L_p=\{xy\in\Sigma^*\mid\delta(q_0, y)=p\text{ and } \delta(p, x)\in F\}$$ ...
- 241
0
votes
1
answer
63
views
prove or give counterexample about regular language
Let $\Sigma = \{a,b\}$, $L_1,L_2\subseteq \Sigma^*$
$L_1 ◃ L_2 = \{w∈ \Sigma^* | \exists v\in L_1, vw \in L_2\}$
For any context-free language $L$, regular language $R$, whether $L \triangleleft R$ ...
- 163
1
vote
1
answer
70
views
Use NFA to express the left quotient of the language of a DFA with respect to the language of another DFA
Let $\Sigma = \{a,b\}$, $L_1,L_2\subseteq \Sigma^*.$
$L_1 \triangleleft L_2 = \{w\in \Sigma^* \mid \exists v\in L_1, vw \in L_2\}$
For clarity, here is python code that shows $L_3 \triangleleft L_4$:
<...
- 163
2
votes
2
answers
62
views
Prove irregularity of a language using closure properties
Given the language $L=\{a^{j+1}b^kc^{j-k}|j\ge k\ge 0 \}$ I need to prove that it is not a regular language using closure properties.
I was having a trouble handling $a^{j+1}$ so I tried to prove this ...
- 241
0
votes
1
answer
62
views
Regular Expression for $L = \{w \mid w\in \{a,b\}^*\text{ and }n_a(w) \equiv 1 \bmod 3\}$
Here, $Σ=\{a,b\}$ The number of $a$ can be $1, 4, 7, 10.....$, also $a$ can be placed anywhere.
Find Regular Expression for $L = \{w \mid w\in \{a,b\}^*\text{ and }n_a(w) \equiv 1 \bmod 3\}$
How can ...
- 9
1
vote
1
answer
35
views
How does + symbol works in regular expression?
What's the difference between $a^*+b^*$ and $(a+b)^*$?
I was going through this question. So according to the question-:
(a+b)* generates $\in$, a,b,ab,ba,aa,ba,...
whereas a*+b* generates $\in$, ...
- 13
1
vote
1
answer
123
views
Regular expression for all strings not containing $aba$
This is my first post here. We are currently studying regular expressions, and I have been tasked to write a regular expression for the language of all words which do not contain the substring $aba$, ...
- 155
3
votes
1
answer
173
views
Proof that a minimal DFA for a finite language has exactly one trap state
Suppose $L$ is a language with a finite number of strings. We know that $L$ is regular. If $M$ is the minimal DFA for $L$, prove that $L$ has exactly one state that we can't exit if we enter it.
I ...
- 61
0
votes
1
answer
29
views
If $L$ is finite and $R$ is not regular, then $R\cup L$ is not regular
Prove/Disprove: If $L$ is finite and $R$ is not regular, then $R\cup L$ is not regular.
I think that this one is true, but I am stuck:
Since $R$ is not regular, it is infinite, so $R \cup L$ is also ...
- 5
0
votes
0
answers
40
views
How to build a DFA that recognizes a language
I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser):
Build a ...
- 17