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
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 ...
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 ...
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 ...
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
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\}^*$?
0 votes
1 answer
65 views

Are all non-context-free language infinite?

Are all non-context-free language infinite?
  • 1
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 (...
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 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 ...
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 \{...
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-...
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$, ...
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, ...
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 ...
-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

1
2 3 4 5
35