Skip to main content

Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
2 votes
2 answers
41 views

Why $(a+b)^* = (a^*b)^* a^*$

I have seen on a book that for regular expressions it holds the equality $(a+b)^* = (a^*b)^* a^*$ but I am not seeing why. It is clear that the language generated by $(a+b)^*$ contains $(a^*b)^* a^*$, ...
Superdivinidad's user avatar
1 vote
1 answer
37 views

How to formally prove that any regular expression can be written as a finite combination of base cases and operations?

In Michael Sipser's book, "Introduction to the Theory of Computation," regular expressions are defined as follows: Based on this definition, how can I formally prove that any regular ...
Vegetal605's user avatar
1 vote
1 answer
37 views

Kleene star of any unary language is regular

I want to prove: Let $L \subseteq \Sigma^*$. If $\Sigma=\{a\}$, then $L^*$ is regular. I found this answer: Kleene star of an infinite unary language always yields a regular language. But I do not ...
shinichi's user avatar
1 vote
1 answer
30 views

How to demonstrate that the intersection of a context-free and a regular language is context-free?

I'm working on a theoretical computer science exercise and need some help with solving it. Here's the task: Task: Let $C$ be a context-free language and $R$ a regular language. Show that $C \cap R$ is ...
Harold 's user avatar
0 votes
2 answers
105 views

Number of a, b and c is even

The language of strings over $a$, $b$ and $c$ such that the number of $a$ is even, the number of $b$ is even and the number of $c$ is even is clearly regular (it is easy to construct a FA or a RE for ...
Marcus's user avatar
  • 141
0 votes
2 answers
50 views

Help regarding a proof in which i am able to prove a regular language $(a(a+b)*)$ as irregular using pumping lemma

I have a regular language $a(a+b)^*$ to which i applied pumping lemma. Let the pumping length be $'p'$ and the example string be $$w=a(a+b)^{p-1}$$. The string satisfies the condition that it is at ...
Dhruv's user avatar
  • 3
0 votes
1 answer
28 views

Is $L = \{\sigma_1 u \sigma_2 v \sigma_3 \mid (\sigma_1, \sigma_2, \sigma_3 \in \Sigma, u, v \in \Sigma^*, |u| = |v|) and ...$ regular

The question asks to determine if any of the following languages above $\Sigma=\left \{ 0,1 \right \}$ is regular. The languages are: $L_1=\left \{ \sigma_1u\sigma_2v\sigma_3:\begin{matrix} \sigma_1,\...
Daniel's user avatar
  • 71
0 votes
1 answer
25 views

Formal regular expression equivalent for this programming regex

Consider these Regexes written in Julia (they should be equivalent in Python): ...
lafinur's user avatar
  • 195
0 votes
0 answers
16 views

Irregular Safety Properties

A regular safety property is a safety property whose bad prefixes form a regular language, https://moves.rwth-aachen.de/wp-content/uploads/WS1920/MC/mc2019_handout_lec4.pdf. My questions is, are there ...
revision's user avatar
1 vote
1 answer
158 views

Why regular languages closed under this operation?

Assume we apply the following operation on the regular language $L$: $$OP(L)=\{a_2a_1a_4a_3\dots a_{2n}a_{2n-1}:a_1a_2a_3\dots a_{2n}\in L\}$$ Why $OP(L)$ remains regular? I think this is as the same ...
ErroR's user avatar
  • 1,942
1 vote
1 answer
51 views

How to prove a function is a bijection (name mangling)?

I'm writing a compiler for a subset of Java, which does not permit overloading (but it does permit overriding). Static functions outside of main are not allowed. We'...
user129393192's user avatar
1 vote
1 answer
65 views

Trying to understand better the solution for $L \ regular \to L'=\left \{ xy^{R}z : xyz\in L\ , x,y,z\in\Sigma^{*} \right \} \ regular$

In this post: For a regular language $L$, is $\{xy^Rz:xyz\in L\}$ regular? @Hendrik Jan have give a really good answer but I'm failing to understand it. I have looked at $L=\left \{ abc \right \}$ in ...
Daniel's user avatar
  • 71
2 votes
1 answer
131 views

Efficiently transforming non-recursive CFG into an NFA

It should be possible to rewrite a non-recursive CFG [1] as an acyclic NFA, since non-recursive CFGs represent finite languages (and thus regular a fortiori). Is there an explicit algorithm to rewrite ...
breandan's user avatar
4 votes
2 answers
122 views

pumping lemma, concatenation of non-regular languages $a \neq b$

Could use some help with the following question. I managed to prove using the pumping lemma that $L_{a \neq b}$, namely amount of a’s not equal to amount of b’s is not regular (using the lemma). But, ...
user169627's user avatar
-1 votes
1 answer
50 views

Regular languages: words from A that do not contain any word from B as a substring [duplicate]

How to prove, by construction and/or regular closures, that if $A$, $B$ are regular then the language $L$ defined by $$L=\{w\mid w\in A,\ \not\exists y\in B\ :\ w=xyz\text{ for some }x,z∈Σ^∗\}$$ is ...
user169627's user avatar
1 vote
1 answer
65 views

Deciding if a regular language is empty can be done in polytime but deciding if it does not accept {0,1}* is not?

In my class we have discussed the fact that, given a representation $\langle R\rangle$ of a regular expression $R$, we can decide whether it accepts any string by first finding an equivalent NFA, and ...
Addem's user avatar
  • 367
0 votes
1 answer
60 views

NFA for $L = \{\sigma_1 u \sigma_2 v \sigma_3 \mid (\sigma_1, \sigma_2, \sigma_3 \in \Sigma, u, v \in \Sigma^*, |u| = |v|) and ...$

The question asks to write a NFA for the following language $L$ above $\Sigma = \left \{0,1 \right \}$. $L = \{\sigma_1 u \sigma_2 v \sigma_3 \mid (\sigma_1, \sigma_2, \sigma_3 \in \Sigma, u, v \in \...
Daniel's user avatar
  • 71
0 votes
1 answer
63 views

Regex for $L = \{ w \mid w \in \Sigma^* \text{ and each substring } u \text{ of } w \text{ where } |u| = 4 \text{ contains the character } 0 \}$

The question asks to write a regex to the following language $L$ above $\Sigma = \left \{0,1 \right \}$. $L = \{ w \mid w \in \Sigma^* \text{ and each substring } u \text{ of } w \text{ where } |u| = ...
Daniel's user avatar
  • 71
0 votes
1 answer
50 views

NFA for a regular expression without $\epsilon$-transitions

I think I know how to convert a regular expression to NFA without requiring epsilon transitions, but I'm not sure if I'm right (I'm just using common sense to be honest, no particular algorithm in my ...
Acad's user avatar
  • 101
0 votes
0 answers
26 views

How to use Jflex to generate a lexer properly?

I was told that making lexer from scrath is really hard and that we should use built in libraries. I used an already existing example to build my program. It worked but was full of error partially ...
Oh No's user avatar
  • 11
1 vote
1 answer
58 views

Constructing a DFA that accepts the set of binary strings with an even length and an odd number of 1s

For this problem, I decided to tackle it by getting the intersection of the DFA that accepts binary strings of an even length and the DFA that accepts binary strings with an odd number of 1s (as seen ...
picato's user avatar
  • 13
0 votes
0 answers
30 views

Proving that $ \{0^i10^i\mid i\geqslant 1\}$ is non-regular, using only closure results and the fact that $\{a^nb^n\mid n\geqslant 0\}$ is non-regular [duplicate]

I've been thinking about this problem for several hours, but I couldn't complete the proof. here is what I did: suppose $L'$ is regular ($L' = \{0^i 1 2^i\mid i \geqslant 0\}$). we define the ...
Ali's user avatar
  • 1
1 vote
2 answers
71 views

Finding the Smallest Language Class containing a given language definition

Given two regular languages L1 and L2 over alphabet Σ, we define the operator RQ(L1, L2) = {w | there exists a word v in L2 such that wv is in L1}. The task is to determine the smallest language class ...
Oh No's user avatar
  • 11
0 votes
1 answer
25 views

Can this Classic Regular Expression be simplified?

I have the following Regular Expression (classic Computer Science definition of Regular Expression, not PCRE or modern computer language RegEx): {(ΣΣ)*00(ΣΣ)*}Σ ∪ Σ{(ΣΣ)*00(ΣΣ)*} It "feels" ...
Diode's user avatar
  • 1
1 vote
0 answers
49 views

A proof that $a^n b^m $ for $n\neq m$ is not regular by using the pumping lemma

I am looking at $L=\{a^nb^m |n\neq m \}$. I would like to prove that $L$ is not regular. This can easily done by assuming it is regular and looking at $\overline L$, or by using other theorems. ...
Eric_'s user avatar
  • 455
1 vote
1 answer
87 views

Draw a finite automation for {w ∈ Σ ∗ | w does not contain the substring 10}

So I am trying to draw a finite automation that has no limits on the length, but cannot have the substring of 10 I created a DFA that could satisfy this requirement,...
cool cat's user avatar
-1 votes
1 answer
77 views

What is the regular language for L = {w | w has even length, and starts and ends with the same symbol}?

I originally thought it was 0(01)*(01)0 U 1(01)(01)1 where: two versions: one that starts and ends with 0, the other that starts and ends with 1 connected by plus, which does not mean union of both ...
cool cat's user avatar
-3 votes
2 answers
46 views

A more concise Finite Automata for 10 substring?

I am learning about finite automata and trying to create a machine that matches {w ∈ Σ∗| w does not contain the substring 10} I created a DFA where it either starts ...
user168855's user avatar
1 vote
2 answers
68 views

Shortest regular expression possible

The question asks to write the shortest regular expression possible to the following automaton: I see only one way to tackle the problem: Use one of the methods mentioned here How to convert finite ...
Daniel's user avatar
  • 71
0 votes
0 answers
18 views

General rules to tell if a language is regular/CFL/decidable/recognizable

I've been looking online for quite some time for some 'general' rules on this. for example, there's a 'rule' that claims that if a language is like $$L={w\in {a,b,c}^* : count_\alpha (w) =count_\beta (...
Aishgadol's user avatar
  • 355
0 votes
2 answers
109 views

regular expression for $\{w\in \{a,b\}^*\mid |w|_a \mod 2 = 0\}\setminus \Sigma^*aab\Sigma^*$

The question asks to write down a regular expression $r$ indicating the language of all the words above $\Sigma = \{a, b\}$ , in which the number of $a$ is even and there is no sub-word $aab$ in them. ...
Daniel's user avatar
  • 71
1 vote
1 answer
65 views

How to show L is non-regular without pumping lemma?

$L=\{(ab)^n : n\text{ is a natural number apart from }6\}$, I want to show L is non-regular by finding an infinite set of L-distinguishable words. Could you help me?
osdinuto's user avatar
0 votes
2 answers
47 views

NFAs that accept a regular language

Just a quick question about regular languages and which NFAs accept them: If I were to draw an NFA that accepts a particular regular language, does that mean the NFA can only accept strings in that ...
Derek Kwon's user avatar
0 votes
2 answers
102 views

how to generate regular expression for the language where symbols have to maintain certain length?

I am having hard time creating regex for languages where symbols must be in certain length. I hope I am not ignorant about rules. we have to generate regex using $^*,|,+ \text{ and }\cdot$ right? I am ...
hxdshell's user avatar
4 votes
3 answers
737 views

Notation in NFA, DFA diagrams and language

I've only recently started learning about deterministic/nondeterministic finite automata and languages and I'd like some clarification on common notation used to describe languages. A 0 or 1 raised to ...
Derek Kwon's user avatar
0 votes
1 answer
35 views

How to handle odd word

Given the language $L = \{ a^n | \text{n is odd} \}$ I'm looking for a word $w$ using $p \in \mathbb(N)$. For example, if it would be even, instead of odd I'd choose $w = a^{2p}$. But with odd, I'm ...
Robert's user avatar
  • 57
2 votes
2 answers
368 views

How to handle multiple exponents (Pumping-Lemma)

Example $L = {(ab)^na^k|n\ge k}$ When searching for a word $w$, using $p \in \mathbb{N}$, for instance $(ab)^pa^p$, but wanting to pump $a$ (which is not possible because $|xy| \le p$ holds), how do I ...
Robert's user avatar
  • 57
1 vote
1 answer
58 views

Does a language dictate the order of the word?

Lets take the Language $$L = \{ (ab)^na^k | n \ge k \}$$ Does it dictate, that the $(ab)^n$ comes before the $a^k$ ? Or is the order irrelevant as long as it matches the $n \ge k$ criterium? In simple ...
Robert's user avatar
  • 57
0 votes
1 answer
44 views

Can we say $|xy^iz| = a^{p+i|y|}b^p$?

Using the Pumping-Lemma for $ \{L = a^nb^n | n \in \mathbb{N}\} $. We define $p \in \mathbb{N}$ It exists a word $w = a^pb^p$ For every $|w| \ge p$: $w=xyz$, $y > 0$, $|xy| \le p$ Because of $|...
Robert's user avatar
  • 57
0 votes
1 answer
42 views

How is $|xy^{2}z| < 2^{p+1}$ (Pumping Lemma application)

In the Question here it is said that $|xy^2z|<2^{p+1}$ Considering that $|x| = 0$ and $|z| = 0$, y consists of $2^{p}$. It's probably trivial, but how do I see, that $|xy^2z| < 2^{p+1}$?
Robert's user avatar
  • 57
2 votes
1 answer
590 views

What does empty string ε actually mean?

I came across this weird expression while learning about regular expressions. $R^+ \cup \varepsilon = R^*$ why does doing union with an empty string makes this regex go from 1 or more to 0 or more?
hxdshell's user avatar
1 vote
1 answer
64 views

Why can't we prove closure under concatenation using DFA?

I can't understand why do we have to use NFA to prove that concatenation operation is closed. According to sisper's book it says that we can't determine where to split the string, i.e. where to ...
hxdshell's user avatar
0 votes
1 answer
54 views

Is the $L'$ regular or not? [duplicate]

Suppose $L$ is regular and we define $L'=\{x:\exists y\in L \wedge \text{ y be a subsequence of x}\}$. Could we conclude that $L'$ is regular or not? I think it's not regular because if $L=a^*b^*c^*$ ...
ErroR's user avatar
  • 1,942
2 votes
1 answer
42 views

Prove that if $L \subseteq b^*$ isn't regular then $M = a^+L \cup b^*$ isn't regular

There is an exercise in a book about finite automata that I couldn't solve: Prove that if $L \subseteq b^*$ isn't regular then $M = a^+L \cup b^*$ isn't regular either, using the fact that REG is ...
Knogger's user avatar
  • 1,222
1 vote
0 answers
28 views

In regular language inference, how is the observation table kept consistent?

I am trying to understand the background literature on regular language inference in the TTT paper ("The TTT Algorithm: A Redundancy-Free Approach to Active Automata Learning" by Isberner, ...
Rahul Gopinath's user avatar
2 votes
3 answers
1k views

Proof that a union of two non-regular languages may be regular

Let $L_1 = \{ a^{n}b^{m} \mid n > m > 0 \} $. Describe a non-regular language $L_2$ such that $L_3 = L_1 \cup L_2$ is regular and $L_3 ≠ A^{*}$ (where $A = \{ a, b \} $) From the trace, I cannot ...
Luca 's user avatar
  • 63
0 votes
1 answer
59 views

Determining the language of a DFA

I've tried quite a large amount of examples, starting from 1 bit all the way up to 5 bits yet I couldn't put my finger on any recurring pattern of words that are accepted. the DFA is as such: The ...
Aishgadol's user avatar
  • 355
1 vote
1 answer
69 views

Proving the set $R$ is finite

Suppose $L$ is a regular language. Let $R\subseteq L$ be a language with maximal size such that for each $x,y\in R$ neither $x$ be a substring of $y$ after removing a substring from $y$ nor $y$ ...
ErroR's user avatar
  • 1,942
0 votes
1 answer
64 views

Proving that the intersection of two languages is regular or not?

Let $B$ and $C$ be two languages on $A = \{a,b\}$: $B = \{ w \mid w \text{ has the same number of }a\text{ and }b\text{ symbols}\}$ $C = \{ a^n b^m \mid n,m \ge 0\}$ Describe $B \cap C$ and determine ...
Luca 's user avatar
  • 63
0 votes
1 answer
35 views

If a person accidentally deletes a few letters when they try to type "IDAHO" or "ILLIONOIS", then when is state name unclear or ambiguous?

The Short Version of my Question The following two regular expressions represent two sets of strings. REGEX EXAMPLES OF STRINGS OF TEXT THAT MATCH THE REGEX ...
Toothpick Anemone's user avatar

1
2 3 4 5
37