Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
-2
votes
2answers
497 views

How to do Big 'O' notations [duplicate]

How can I solve $\mathcal{O}$-notations without using Java or any other programming language? I only want to use pen and paper.
-2
votes
1answer
40 views

Some problem about regular language

Let's say $\alpha$ is simple word if it couldn't be represented as $\beta^{n}$($n$ times concatenation of $\beta$), where $\beta \ne \alpha$ Consider two sets: $p_{N}(L) = \{\alpha^{n} | \alpha \in L ...
-2
votes
1answer
97 views

what is the regular expression for this language?

the language is: L={{0,1}*|strings that contain the same number of 1's and 0's , plus there can't be three (or more) aces or zeros one after another} for example the string cannot be: 111001 because ...
-2
votes
1answer
88 views

Regular language subsets [duplicate]

If $L_{1} \subseteq L_{2}$ and $ L_{2}$ is regular, does it follow that $L_{1}$ is necessarily regular? I don't understand this question, is there any proof to show this or is there an assumption we ...
-2
votes
1answer
87 views

What is the minimal states for the language DFA?

Let the language $$L = \{ w: \text{ for any prefix } u \text{ of } w : \left|\#_o(u) - 2\cdot \#_1(u) \right| \le 2 \}$$ What is the minimal number of states for a DFA, accepting $L$? $4$...
-2
votes
1answer
437 views

How to write this regular expression

Consider the language over the alphabet $\sum= \{a\}$ containing strings whose length is either a multiple of 2 or 3 (including the empty strings). Writing a regular expression for this language
-2
votes
1answer
200 views

Prove that X/Y/Z is context-free

Given languages X, Y and Z, each with alphabet, define X/Y/Z as: X/Y/Z = { w ∈ Σ* | ∃u ∈ Y and ∃v ∈ Z; such that wuv ∈ X }. Prove that if X is context-...
-2
votes
2answers
101 views

Context free Grammar for this context free language

How can I create a context free grammar for the language $\{p^2q^mpr^nq^{2n+m}| m,n \ge 0\}$, where $\Sigma = \{p,q,r\}$?
-2
votes
1answer
221 views

Pumping lemma for regular languages proof

I'm trying to prove that if P(L,n) is true then L is regular, where P(L,n) is a property equivalent to the pumping lemma. This is in the context of single letter alphabet. Any suggestions how to do it?...
-2
votes
1answer
550 views

$\{0,1\}^*$ vs $\{0,1\}^+$ vs $(0 \cup 1)^*$

I understand that $(0 U 1)^*$ is the set of all binary strings. However, what do the other two expressions create? Could someone please provide examples of what strings these languages would accept? ...
-2
votes
1answer
4k views

How do you prove Sigma Star is regular

I noticed in another answer on this forum Note that the languages ∅, {ϵ} and Σ* are regular. How do you prove Sigma Star is regular.
-2
votes
1answer
78 views

Regular expression of a given language [closed]

Could somebody please confirm if a regular expression of language: $$ L := \{b(ab)^n a^m \mid n, m \geq 0\} $$ is $$\{b, (ab)^* a^*\}? $$ And if not, could somebody please tell me why?
-2
votes
1answer
57 views

Is language regular?

Suppose we have language $a^{\binom{n}{k}} n,k \in N$ is this language regular ? If it is not, I should use pummping-lemma? It it is regular, I will use proof by induction ?
-2
votes
1answer
565 views

Union of two languages [closed]

If I have these languages: $$\begin{align*} S&=\{a,b,c,d,e,f,g,h\}\\ A&=\{b,g\}\\ B&=\{a,b,c,d,f,h\}\\ C&=\{a,c,g\}\,, \end{align*}$$ Writing $X'$ for the complement of a set $X$, ...
-2
votes
1answer
264 views

Kleene star of L

$L^*$ is the kleene star of L. say we have a def: $L^*$ = $L^0$ U $L^1$ U $L^2$ U ... U $L^K$ then prove that: $L^*$ = $L$ if and only if $L$ = $L$ o $L$ how do i prove this?
-2
votes
1answer
892 views

Convert regular expression to FA?

I am trying to solve a practice problem from my textbook which is to draw an FA from this language: L(ab* a*) U L((ab)*ba) I need help to draw the second part L((ab)*ba). I know the shortest string ...
-2
votes
1answer
108 views

Is the language given by this CFG regular? [duplicate]

S → AB | C A → aAb | ab B → cBd | cd C → aCd | aDd D → bDc | bc How can I prove that this language is regular or not? I need your help. It also has two ...
-2
votes
1answer
163 views

Prove that $(L^*M^*)^* = (L\cup M)^*$

I would like to find out how to prove this statement. Thank you. Well I think that I proved one part of the statement, but my proof doesn't really look elegant. My proof of $(L\cup M)^* \subset (L^*M^...
-2
votes
1answer
9k views

Regular expression for all strings with at least two 0s over alphabet {0,1}

My answer : (0+1)* 0 (0+1)* 0 (0+1)* Why is this incorrect? Can somebody explain to me what the correct answer is and why?
-3
votes
1answer
123 views

Prove A² is regular [duplicate]

Suppose that $A$ is a regular language. How can I show that $A^2 = A \cdot A$ is a regular language? Is there a construction?
-3
votes
1answer
132 views

Regular and context free languages

I need to determine if the following languages are regular / context free and to explain. Please help me with that. $$L_1 = \{ a^{i_{1}}b a^{i_{2}}b a^{i_{3}}b a^{i_{4}}b a^{i_{5}}b a^{i_{6}}b a^{i_{...
-3
votes
2answers
3k views

Are all irregular languages infinite? [duplicate]

How can I prove whether irregular languages are infinite? I thought about proving it by the definition of regular language but got stuck.
-3
votes
1answer
50 views

The language of all base-10 integers that are multiples of 9 [closed]

If I want to represent all the base 10 integers that are multiples of 9 as a language how do I do so? Alphabets are finite sets.
-3
votes
1answer
119 views

The set of all words containing more 1's than 2s [closed]

I'm currently working through some regular expression questions and I've got a solution for one of the problems that I'm not certain is correct. The question has this preface. We only consider ...
-3
votes
1answer
96 views

Show whether the language with almost as many 0 as 1 in every prefix is regular [closed]

This is the exercise: Let A be a language defined over the alphabet Σ = {0, 1} composed by the strings with the property that in every prefix, the number of 0s and the number of 1s differ by at ...
-3
votes
1answer
98 views

Give three words that are in the language of the first and second regular expression [closed]

This is our alphabet: $\{0,1,2\}$ And lets say I have two regular expressions: Regular expression 1. $(1|22|0)^* (2|0)^*$ Regular expression 2. $(0|1)^* (1|20|1)^*$ How can I give three words each ...
-3
votes
1answer
90 views

Step by step method for generating Regular Expressions for languages [duplicate]

I was wondering if there was a method that can be used to generate a Regular Expression for a language. Take the Language $L$ as an example where: $L= \{w \in \{0, 1\}^{\ast} \mid \text{length of } w ...