Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
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, ...
user avatar
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\...
user avatar
  • 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.
user avatar
-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
user avatar
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 ...
user avatar
-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 ...
user avatar
  • 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 $\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 \...
user avatar
  • 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!
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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$...
user avatar
  • 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 ...
user avatar
  • 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!
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 -> ...
user avatar
-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?
user avatar
  • 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\...
user avatar
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?
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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}$ ...
user avatar
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 ...
user avatar
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, ...
user avatar
  • 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&...
user avatar
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 ...
user avatar
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|=...
user avatar
-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 ...
user avatar
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, ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
  • 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^...
user avatar
  • 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$ $...
user avatar
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\}$$ ...
user avatar
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$ ...
user avatar
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$: <...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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$, ...
user avatar
  • 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$, ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar

1
2 3 4 5
34