Questions tagged [regular-language]

Question 1

Is a set consisting of strings such that x is of prime length or x is of odd length regular? What about if x is prime length or x is even length? My intuition says no because $L_p = \{x | |x| is prime\...

Question 2

Is the language {xyx, where x,y are arbitrary strings over {0,1}} a regular set? I'm not sure on this, but I think it is regular. Let $x=\epsilon$, then $xyx = y$ and $y=\{0,1\}^*$.

Question 3

I've got following statement (as a challenge, not as a hw or something), being told that it's kinda hard to prove it $ L = \lbrace a^m b^n \mid m \neq n^2 \rbrace $ isn't CFL Following statement (...

Question 4

"For a symbol a, define a+ = {a,aa,...}. Is the language L = {wcwR|w,c ∈ {a,b}+} regular? Here, wR is just w reversed. If your answer is yes, write the equivalent regular expression, and if no, ...

Question 5

Consider the language of those $w\in \{a,b,c,d\}^*$ that contain $ab$. Corresponding DFA is (written in SageMath): ...

Question 6

Fix a finite alphabet $A$. The set of regular languages is the smallest set of languages on $A$ (i.e. subsets $L$ of the free monoid $A^*$) containing $\varnothing$ and the singletons $a$ for $a\in A$ ...

Question 7

I am studying for exams, and previous years had these two problems that I have conflated in the title. Problem 1) For every regular language $ L \subseteq \Sigma^*$ over $\Sigma$, $\mathcal{H}(L)$ is ...

Question 8

Suppose that First-order logic sentence is a string described by the following rules : $[a-z]$ - is a First-order logic sentence if $\phi, \psi$ are First-order logic sentences, then $$(\neg \phi) \...

Question 9

My professor tends to prove a language L is not regular using contradiction, i.e: Assume L is regular $\implies$ L can be pumped Show that L cannot be pumped Contradiction, so initial assumption is ...

Question 10

I was given this problem on regular languages, which I solved, but I was wondering there is another, more elegant way to approach it. I'll share the problem first, along with my solution, and then ...

Question 11

These are the two initial DFAs, and I need to construct a DFA that recognizes the intersection of the two languages accepted by the given DFAs, using closure properties. Here is the first DFA: And ...

Question 12

Given the language $A=\{(01)^n|n\in\mathbb{N}\}$. The following attempt for a proof of its irregularity was outlined: "Suppose for the sake of contradiction that $A$ is regular. Thus, it has some ...

Question 13

Prove using the Myhill-Nerode theorem that the language $L = \{xyz| x,y \in\{a,b\}^+\}$ - is not regular My answer: To prove that $L$ is not regular, we need to show that there are infinitely many ...

Question 14

good day. I am very new to automata theory and currently studying by myself. I studied regular and now context free grammar and I believe I may have understood most of it, but I still can't pinpoint ...

Question 15

I am looking for a grammar or algorithm to write down what I now call 'metacompositions' (or just compositions of compositions? see https://oeis.org/A133494) of character strings with the absolute ...

Stack Exchange Network

Questions tagged [regular-language]

Is a set consisting of strings such that x is of prime length or x is of odd length regular? What about if x is prime length or x is even length? [closed]

Is the language {xyx, where x,y are arbitrary strings over {0,1}} a regular set?

Prove that $ L = \lbrace a^m b^n \mid m \neq n^2 \rbrace $ isn't CFL

Proving whether a language L is regular or not using the pumping lemma (and some intuition)

SageMath's Automaton method number_of_words error

Constructions of regular languages

Prove that for every regular language/CFL $L \subseteq \Sigma^*$ over $\Sigma$, $\mathcal{H}(L)$ is also a regular language/CFL

Is First-order logic regular?

Valid application of the pumping lemma for regular languages?

How to derive a procedure to perform bitwise OR between two regular expressions

Intersection of 2 deterministic finite automatons (DFAs)

Pumping Lemma - string partitioning

Prove not regularity of a palindrome using Myhill-Nerode [closed]

CFG Pumping Lemma x Regular Language Pumping Lemma - What exactly are we analyzing in the Case Proofs?

Compression of metacomposition strings (https://oeis.org/A133494)

Hot Network Questions