Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,722
questions
0
votes
1
answer
31
views
Regular grammar such that it rejects keywords
I want to write a regular grammar that follows the C language. I almost wrote the grammar, but was not able to resolve how to define a variable.
Def: A variable can be any combination of characters, ...
- 1
0
votes
2
answers
45
views
If L = L1 U L2 is regular, L2 is the complement of L1 (which means L1 ∩ L2 = Ø), and we're given that L and L2 are regular, is L1 regular?
L1, L2, and L are not finite. We're given that L and L2 are regular. However, L1 ∩ L2 is empty, since L2 is the complement of L1.
Is L1 regular under the property that regular languages are closed ...
- 1
0
votes
1
answer
38
views
Using the pumping lemma, show that L = {a b^n c^n | n ≥ 0} is not regular
I've encountered many examples which its format is like: a^n b^n. For this I understand that w = 2n and is pretty straightforward, but what happens in my case? Is w = 1 + 2n? And in this case would |...
-3
votes
0
answers
21
views
deterministic finite automata for (a(ab|bb)*(aa|c))*
i am trying to make Deterministic Finite Automata (DFA) of this lang (a(ab|bb)^*(aa|c))^ but i don't know how to do it.
does anyone know how to create dfa that recognizes this language?
- 1
0
votes
0
answers
29
views
Complement of a language definition
Let $A=\{$ M is a TM, $s\in \mathbb{N}$ and $\exists x\in\Sigma^*$ s.t M rejects $x$ in at most $s$ steps $\}$.
I want to define its complement, so how do I negate "$\exists x\in\Sigma^*$ s.t M ...
- 19
4
votes
0
answers
63
views
Inverse operation to concatenation for regular languages
I'm currently in need of the inverse operation of the concatenation of 2 regular languages.
Formally, for 3 regular languages $A,B,C$ such that $A \cdot B = C$, only $A$ and $C$ are known, and $B$ is ...
- 103
0
votes
1
answer
31
views
Why must 2 distinct strings go to the same state in a DFA?
I'm finding it difficult to understand why due to the pigeonhole principle, 2 distinct words must go to the same state in a DFA.
Is it that if there are n words and m states, where there are more ...
- 1
0
votes
1
answer
48
views
Proving L1 ∪ L2 ⊆ L1* L2*
I'm stuck here, how can i prove this:
$$L_1 \cup L_2 \subseteq L_1^*L_2^*$$
$$\begin{array}{rcl}
x\in L_1\cup L_2 & \Rightarrow & x\in L_1^* \lor x\in L_2^*\\
&\Rightarrow &x\in L_1^*\...
1
vote
1
answer
40
views
Shuffle of a DCFL and a regular language
This is problem 88 from Miscellaneous exercises of Kozen's "Automata and Computability".
The shuffle $A||B$ of two languages $A$ and $B$ is defined as $\{w \mid w = a_1b_1\ldots a_kb_k,$ ...
- 13
0
votes
2
answers
41
views
Regular language under intersection and complement confusion
I know that regular languages are closed under closure properties. But, for example, we know if $L$ is regular, then its complement $L^\complement$ is also regular. If we have $L_1$ and $L_2$ as ...
- 31
0
votes
2
answers
56
views
Language to regular expression to prove it is regular
I'm trying to find a regular expression to describe the following language:
$\{a^n xa^n | n≥1,x ∈ Σ^* \}$
where $Σ$ = {a,b}
So far I've come up with
$aa^* (aUb)^* aa^*$
but I don't think that accounts ...
- 103
-1
votes
0
answers
33
views
regular expression: every 00 must have 11 before it [duplicate]
How would you approach defining a regular expression on $\Sigma = \{0, 1\}$ that matches this property: every pair of $00$ must have $11$ immediately before it?
- 31
-3
votes
0
answers
17
views
what is the regular expression for language that dosen't contain abba [duplicate]
what is the regular expression for language that doesn't contain abba in a DFA
- 1
2
votes
1
answer
34
views
How to prove that for any words $w_1, ..., w_n$ of alphabet $\{0,1\}$ regular expression $w_1^*w_2^*...w_n^*$ doesn't represent language $\{0,1\}^*$?
How to prove that for any words $w_1, ..., w_n$ on alphabet $\{0,1\}$ the regular expression $w_1^*w_2^*...w_n^*$ doesn't represent language $\{0,1\}^*$?
- 131
0
votes
1
answer
65
views
0
votes
1
answer
48
views
Show that the the language $L = \{0^kww0^m | k,m \ge 1, w \in \{0, 1\}^*\}$ is nonregular
Caveat. You have to show this specifically by showing there exists an infinite set that is pairwise distinguishable with respect to L.
This question was on a quiz which we had 12 minutes to complete (...
- 1
0
votes
0
answers
26
views
Show non regularity of a language using closure property
Show that the language $\{0^n1^m0^n| m,n\in \mathbb{N}\}$ is not regular using closure properties.
I tried showing this using pumping lemma but I am stuck when it comes to closure properties. Please ...
- 1
0
votes
1
answer
24
views
How to use BNF for {a^n b^n | n>0}
so I know that this language is not regular, however, can you still define the language using BNF? This is the problem:
{a^n b^n |n>0}
0
votes
0
answers
23
views
Regular expression for strings that do not contain the substring $aa$ and contain an even number of $a$'s [duplicate]
I am trying to find the regular expression for the set of strings over the alphabet $\{a,b\}$ that:
do not contain the substring $aa$ and
contain an even number of $a$'s
Such examples include:
$...
- 1
-1
votes
1
answer
43
views
Prove that $L ⊆ \{a, b\}^∗$ is a regular language then language $K ⊆ \{a, b, \#\}^∗$ is also regular
Suppose $L ⊆ \{a, b\}^*$ is a regular language.
Show that the language
$K ⊆ \{a, b, \#\}^*$ defined by,
$$K = \{x_1 · \#·x_2 · \#··· \#·x_n | n \ge 0,x_i ∈ L\}$$
is also regular.
I have no idea how to ...
0
votes
1
answer
63
views
Is my DFA optimal?
I designed this FSM graph to demonstrate a DFA that would accept any string that
is of length 5,
must contain a d,
can only have as and/or bs before the d, and
can only have bs and/or cs after the d.
...
- 103
0
votes
1
answer
42
views
Regular Language to Regular Expression
Let's assume I have the following regular language:
L = {1,0}*{010}{1,0}*
I would like to convert this to regex for a program. Would the equivalent regular expression for this be:
((0+1)*(010)(0+1)*)
...
9
votes
4
answers
1k
views
Non-regular language whose prefix language is regular but not the whole set of words
I've seen some questions regarding the regularity of prefix language of non-regular languages (for examples, here and here). In both cases, the prefix language ended up just being the whole set of ...
- 381
0
votes
1
answer
38
views
Does $L = \{a^n \ | \ n \geq 1, \ n \ \text{ is even or a square number}\}$ have infinite equivalence classes?
I am unsure if it has infinite equivalence classes or not, respectively how to interpret the textbook solution.
My approach was that it has infinite because,
lets say we have $x = a^5$ and $y = a^7$.
...
- 7
0
votes
2
answers
67
views
Show for every $CFL$ $L$ that's not $REG$ exists $L_1,L_2$ with $L_1$ is $REG$ and $L_1 \subseteq L_2$ and $L_2$ is not $REG$ and $L \subseteq L_2$
i want to show that for all $CFL$ and not $REG$ languages $L \subseteq \{0,1\}^*$
exists $L_1,L_2\subseteq\{0,1\}^*$ with:
$L_1$ is $REG$
$L_2$ is $CFL$ and not $REG$
$L_1 \subseteq L_2 $
$L \...
- 7
0
votes
0
answers
48
views
proof that there exists a regular expression r for every NFA with only 2 states
Let L be a regular language. Then there exists a regular expression r such that L = L(r).
Proof for NFAs with only 2 states (can be generalized!), partly seen during a lecture and completed by me:
Let ...
- 89
8
votes
1
answer
88
views
Is every $p$th word in a regular language regular?
Question
Let $L$ be a regular language. Let's say we sort $L$ by length and then lexicographically; then let $L_p \subset L$ be every $p$th word in $L$ according to this sort. Is $L_p$ regular as well?...
- 356
1
vote
1
answer
130
views
pumping lemma length restrictions clarification
I know that this kind of question has been asked before, but I still see different kind of answers getting multiple upvotes, but I am not sure if they are all correct. That’s why I wanted to ask it ...
- 89
2
votes
1
answer
70
views
minimal DFA transition function clearification
Statement:
Given any dfa $M$, application of the procedure 'reduce' (see below) yields another dfa $\hat{M}$ such that $M$ and $\hat{M}$ are equivalent. Furthermore $\hat{M}$ is minimal in the sense ...
- 89
0
votes
1
answer
27
views
Extended transition function in NFA
The following statement seems trivial, but how can it be formally proven/argued?
$$\bigcup_{s \in \delta_{N}^{*}\left(q_{0}, w\right)} \delta_{N}^{*}(s, a) \;\equiv\; \delta_{N}^{*}\left(q_{0}, w a\...
- 89
1
vote
1
answer
45
views
Are both regular expressions correct for the given DFA with three states?
Are both regular expressions correct for the following automaton?
$$(\lambda+ a a^*b(ab)^*)(\lambda + b(a+b)^*)\\
\ \\
(a a^*b)^*(\lambda + b(a+b)^*)$$
The first one is the solution provided by the ...
- 89
1
vote
2
answers
52
views
Optimal way to construct union automata of two DFAs
Given two DFAs, is it also a correct method to start with the combination of the initial states of both automata, then check where I can go for each symbol from these two states. Then add the ...
- 89
0
votes
1
answer
81
views
proving a step in the proof of regular intersection
Let $L_1$ be a context-free language and $L_2$ be a regular language. Then $L_1 \cap L_2$ is context-free.
Part of a proof given in the book "Formal languages and automata":
Let $M_{1}=\left(...
- 89
17
votes
5
answers
3k
views
Regular languages that seem irregular
I'm trying to find examples of languages that don't seem regular, but are. A reference to where such examples may be found is also appreciated.
So far I've found two. One is $L_1=\{a^ku\,\,|\,\,u\in \{...
- 381
1
vote
1
answer
101
views
Comparing automata sizes given Myhill-Nerode equivalence under a function
Consider two finite languages, $L_A$ over alphabet $A$ and $L_B$ over alphabet $B$. $A$ might be the same as $B$.
Since $L_A$ and $L_B$ are finite languages, there exist minimal acyclic deterministic ...
- 820
0
votes
2
answers
379
views
Regex for string does not contain the substring "110"
Can anyone help me figure out the error in my approach to this problem from Sipser 1.18 (1.6f)?
Write a regular expression for the language L = {w | w does not contain 110}
So, the answer I get is: $(...
- 33
1
vote
1
answer
96
views
determining whether a context-free language is regular
I was wondering how to determine (with proof) whether the context-free language generated by the following context-free grammar $G$ is regular, where $S$ is the start variable and $a$, $b$ are the non-...
- 279
0
votes
1
answer
35
views
Confused by Sipser's proof of equivalence of R and NFAs
I am reading Introduction To Theory of Computation by Sipser, 3rd Edition and am confused by his take on the last three cases of proving that "if a language is described by regular expression ...
- 33
1
vote
1
answer
133
views
Prove a subset of a regular language is regular, context-free but not regular or not context free
I've been tasked with solving this problem, but I'm not sure where to begin:
Let $L$ be a context-free language. $L'$ contains all the words that belong to $L$ which can't be defined as $z=uvwxy$, ...
- 113
1
vote
1
answer
73
views
State Complexity of DFAs for Restricted Languages
Let $\Sigma$ be a finite alphabet. All strings below are over $\Sigma$.
Definitions:
If a string $s = vw$, then $v$ is a $\textit{prefix}$ of $s$ and $w$ is a $\textit{suffix}$ of $s$.
For a language $...
- 820
1
vote
1
answer
73
views
Myhill-Nerode equivalence under a function
Consider two finite languages, $L_A$ and $L_B$, potentially over different alphabets. Now since these languages are finite, there exist minimal acyclic deterministic finite-state automata to decide ...
- 820
0
votes
1
answer
75
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
86
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
1
answer
48
views
How to use Pumping Lemma $L = \{ wsw \mid w \in \{0,1\}^*, s \in \{2\}^* \text{, and } |w| = 2 \cdot |s| \}$?
I'm trying to use the Pumping Lemma to prove that $L = \{ wsw \mid w \in \{0,1\}^*,\ s \in \{2\}^*\text{ and } |w| = 2\cdot|s| \}$ is not a CFL.
1
vote
1
answer
87
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
49
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 ...
- 239
0
votes
0
answers
25
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 $\...
- 239
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 ...
- 239
0
votes
0
answers
33
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 ...
- 239
4
votes
1
answer
91
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 \...
- 356