The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
0answers
18 views

How to solve the following relationship?

We can easily seen that $${q^{2n}} = {q^n}\left( {{q^n} - 1} \right) + {q^n},{q^{3n}} = {q^n}{\left( {{q^n} - 1} \right)^2} + 2{q^n}\left( {{q^n} - 1} \right) + {q^n}.$$ Similarly, we assume that ...
0
votes
1answer
40 views

Writing regular expressions

So here's the problem: Let $Σ =\{a, b, c\}$. Write a regular expression for the set of all strings in $Σ^∗$ such that the sum of the number of $a$’s and $b$’s in the string is at most two. Thus the ...
0
votes
1answer
39 views

Give some examples of strings in, and not in, these sets, where Σ = {a,b}

Here's the set: {w : for some u ∈ Σ*, www = uu} From what I understand, it's saying "w (which is a string) such that for some u (which is another string) is an element of the possible combinations ...
1
vote
0answers
40 views

Rewriting regular expressions

For the following two regular expressions, how would I rewrite them as a simpler expression representing the same set? $b^* \cup a^* \cup (a \cup b)^*$ $\Big((a^*b^*)^*(b^* \cup a^*)^*\Big)^*$ I ...
2
votes
1answer
641 views

Finite state machine

I am doing discrete math, and we are studying Finite State Machines. But i am a little confuse on how to do this. Here is a question, Write a regular expression for the language, and define a finite ...
1
vote
1answer
22 views

examples of “interesting” star-free languages

Can you point me to some examples (preferably known ones from the literature, but this is not crucial) of "interesting" / non-trivial star-free languages? I'm trying to get some intuitive sense of ...
-1
votes
2answers
47 views

Prove that $R_1 \times R_2$ is a regular language for $R_1, R_2$ regular [closed]

Let A and B be two sets. The cross products of A and B are defined as : AxB={(a,b): a belongs to A and b belongs to B }. Assume R1 and R2 are regular languages over an input alphabet Σ={a,b}. Prove ...
0
votes
1answer
25 views

What is $h^{-1}(L)$, for $L$ a regular language and $h$ a homomorphism?

Let $L = L((00 + 1)^∗)$ and $h : \{a, b\}^* \to \{0, 1\}^*$ be defined by $h(a) = 01$ and $h(b) = 10$. What is $h^{−1}(L)$? In this context "$+$" means "$\cup$". So the language $L$ is all the ...
1
vote
1answer
22 views

Creating a regex expression for a regular language

$\{x \in \{0, 1 \} : x = 0^m1^n \hspace{.1cm} \text{for some} \hspace{.1cm} m, n \in N \hspace{.1cm} \text{such that} \hspace{.1cm} m * n \ge 3\}$. I've been stuck on trying to create a regex for ...
0
votes
1answer
796 views

Palindrome Decidable by DFA

Here's a problem a professor I was talking with gave to me to see how people solve. How would you solve this? A string in {a,...,z}* is said to be a palindrome if it is equal to its own reversal. Is ...
0
votes
1answer
308 views

Induction to prove regular expression

Prove that is if S and T are any regular expressions over the one-letter alphabet, (for example: Σ = {a}), and if n is any natural, then the languages (ST)^n and (S^n)(T^n) are equal. I have to use ...
0
votes
5answers
62 views

Regular Expression for Simple Language

I'm having trouble writing a regular expression given the following $\{a, b, c\}$ which produces the set of strings of length 3. I don't really understand how to restrict the length of the string. ...
1
vote
1answer
17 views

Using induction to prova a regular expression belongs to the language generated by a grammar (well half-proving anyways)

I have a grammar with this productions S->aBSBBa |$ \epsilon $ B->bB|$\epsilon$ $L(B)=b^*$ (by Arden's rule) and seems that $L(S) = a(b+ab^*a)^*a + \epsilon$ I have to prove that last ...
1
vote
1answer
21 views

Arden rule proof

I'm studying Arden's Rule for regular languages, but I'm having troubles with the proof. Arden's rule states that the set A*⋅B is the smallest language that is a solution for X in the linear equation ...
1
vote
1answer
16 views

Is Σ* the same as saying L*

I'm getting confused over the two. Are they the same? The complement of a language L is Σ* - L. Is saying L* - L wrong?
0
votes
1answer
16 views

Proving that a language with a regular expression is context-free

If L = {ww : w ∈ L(1*01*)} it means that w = $1^a$0$1^b$ and ww = $1^a$0$1^b$$1^a$0$1^b$ If I want to prove that this language is context-free by giving a context-free grammar, can I give a CF ...
0
votes
1answer
27 views

Regular expression

I'm trying to find Strings of length 4 In this regular expression. However, I'm having trouble understanding how the string is built $$1(1+00)^*0+(01)^*+(101+0)(10+λ)1^*$$ For example, for ...
1
vote
1answer
49 views

Find regular expression that defines a given language

I want to find a regular expression that defines a language L over the alphabet {0,1} with a following condition: every word contains exactly two 000 substrings. For example, a valid word would be ...
2
votes
1answer
19 views

Finding regular expressions for which a given Turing machine halts and accepts, halts and rejects, and diverges.

Consider the Turing machine M = (Q,Σ,Γ,δ,q,F) F = {t} Q = {q,r,s,t,v,x} Σ = {a,b,c} Γ = {B,a,b,c} δ = [q,a,q,a,R] [q,b,q,b,R] [q,c,v,b,R] [q,B,r,B,L] [r,a,s,B,L] [r,b,s,B,L] [r,c,s,B,L] ...
0
votes
1answer
58 views

How would I draw a state transition diagram to satisfy this regular expression?

I somewhat understand finite state machines in concept however am unsure how I would apply it in this example. The question is Draw the transition diagram of a finite state recogniser which accepts ...
0
votes
1answer
34 views

Regular Expressions that define given languages

A few of these here I just wanted to make sure I had right. For $\Sigma = \{0,1\}$ a. The language consisting of all strings of 0's and 1's that have even length and where 0's and 1's alternate I ...
2
votes
3answers
63 views

The number of elements in a set

I have a small task, part of my homework, which tends to confuse me because of its simplicity. It makes me think that I am missing something. I have to find the number of elements in the set {w | w ∈ ...
0
votes
2answers
125 views

Describe as a regular expression the set of strings over {a,b,c} that contain the substrings aa,bb,cc

What would be an appropriate regular expression for this set of strings listed in my title? i have this so far: (aa,bb,cc) is a subset of all the strings listed (a,b,c) (it corresponds to the strings ...
0
votes
3answers
2k views

Regex for strings with no three identical consecutive characters

I wanna ask what the regular expression for the strings having the property in the title should be. For binary string with no three consecutive 0, it's quite a simple regex ...
0
votes
1answer
24 views

Constructing regular expressions for languages

I'm new to regular expressions and I'm currently working on some exercises to get familiar in constructing regular expressions for languages. I have the following languages, for which I already tried ...
0
votes
2answers
19 views

Languages and their Regular Expressions - Automata

I am working on some Automata practice problems. I am working a 2 part question. Here it is: Let $\Sigma = \{a,b\}$ be an alphabet. Let $L = \left\{w \in \Sigma^* \mid n_a(w) \le 4\right\}$ ...
2
votes
2answers
46 views

A Regular Expression for all strings that…

I got a problem I have to solve, the problem says that given an alphabet $\Sigma = \{a, b, c\}$ I have to build a regular expression that describes the string with: An even number of a's. A 4k + 1 ...
0
votes
1answer
66 views

Proving that two expressions are equivalent

So, I'm working through some proof exercises, and one of the questions is about the following regular expression: (a|b)* = a*(a|b)* if they are equivalent, prove ...
0
votes
1answer
45 views

Convert the regular expression to a NFA

I have to convert the following regular expressions to a NFA: $$(0 \cup 1)^{\star} 000 (0 \cup 1)^{\star}$$ $$(((00)^{\star} (11)) \cup 01)^{\star}$$ $$\emptyset^{\star}$$ $$a(abb)^{\star} \cup ...
0
votes
0answers
31 views

Derivation: Discerning difference between arithmetic expression with parenthesis versus without using abstract syntax trees

I am trying to illustrate the expression: ( 3 * 4 + 5 * 6 + 7 ) using an abstract syntax tree. I have already illustrated the expression: ( 3 * (4 + 5) * (6 + 7) ). Could someone please illustrate ...
2
votes
1answer
35 views

Equivalence of regular expression

Let $ A = \{a,b\}$ be an alphabet. Please hint me with show, that this regexes are equivalent. That means, we should show that: $L(e_1 )= L(e_2)$ 1) $(a^*b)^*a^* = (a+b^*)^*$ 2) $(a+b^*)^* = ...
2
votes
1answer
742 views

Complement of a regular expression?

What is the regex for the complement of $r = b^*(ab + a^* + abb(b^+))^*$ ? I am thinking $(a+b)^*(abb)^+a^* $ since anything that contains $abb$ and is not followed by $b$'s would not be accepted ...
1
vote
1answer
31 views

Difference between regular and not regular languages

I don't understand the difference, in classes I've seen the pumping lemma for regular languages and I know how to apply it to demonstrate whether a language is regular or not, but I feel that I don't ...
2
votes
1answer
57 views

NFA to DFA and Regular Expression

The truth is that my teacher gave us a homework, and I wanted to ask you if I did this right. What I have to do is answer the following questions given the following NFA. Why is this an NFA? What ...
1
vote
1answer
86 views

Find regular expression for a given language

I need to find a regular expression for the following language: $$ \Sigma = {\{a,b,c}\} $$ define $L$ to be the language of all words over $\Sigma$ that contain the substring $aba$ odd number of ...
0
votes
1answer
48 views

Proving an operation is closed under regular languages

Following operation is defined over languages where $n \in \mathbb{N} :$ $L \ominus n = \lbrace s \in \sum^* | \exists s^{'} \in \sum^* (length(s^{'})=n,ss^{'} \in L) \rbrace$ Meaning that $L ...
1
vote
2answers
42 views

Proving {0^n 1^n 2^n | n >= 0} is not regular

This is not a homework assignment, but something I'm reviewing. I need to prove that $0^n 1^n 2^n$ where $n \geq 0$ is not regular (Just the DFA, not related to CFG). I feel like this is similar to ...
1
vote
1answer
49 views

Write the regular expression of the language that the DFA accepts.

I am given a DFA and I have tried to write the regular expression of the language that it accepts. This is the DFA that I am given: I have found some words that the DFA accepts: ...
0
votes
2answers
35 views

Finding the regular expression

I have the problem below: I need to find the regular expression of the set of strings where $n(a)+n(b)$ is an even number (where $n(a)$ is the number of $a$'s and $n(b)$ is the number of $b$'s) .. I ...
0
votes
2answers
66 views

Determine whether $L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\}$ is regular.

Given the alphabet $\Sigma=\{a, b\}$ and for the next Language $L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\}$ determine whether the language is regular. Firstly, I think this language is regular. ...
0
votes
0answers
29 views

One-to-one correspondance between regular sets

I have problem with one-to-one correspondance "One-to-one correspondence with the set (B) of all tags possible being represented with their binary representation (i.e. 0, 01, 00, 010101, 11000, ...
1
vote
1answer
47 views

Regular expressions

I have this assignment and I have to prove that $$ (b+aa^* b)+(b+aa^* b)(a+ba^* b)^* (a+ba^* b) = a^* b(a+ba^* a)b^* $$ How do I prove this? What I have is this: $$\begin{align} \text{LHS} ...
2
votes
0answers
34 views

Regular expressions and equality

Is the equality true or false? $(r^*s^*)=(r+s)^*$ My Approach: Assume the alphabet used is {0,1}$^*$ Equality is false: If r = 0 and s = 1 Then if 0101 $∈$ $(0 + 1)^*$ this is true because ...
1
vote
1answer
11 views

Regular expression building: Comment delimited strings

I'm attempting to build a regular expression that will accept only strings of the form: ...
0
votes
1answer
58 views

Proving Reversal of a Language in Recursive Way

We define the $reverse$ of a string as follows: $(x_1x_2...x_n)^R=x_nx_{n-1}...x_1$ where $x_1,x_2,...,x_n \in \Sigma$. We can also define the reverse of a language by $L^R= \lbrace s' | \exists s ...
0
votes
1answer
20 views

Clarification on Lemma problem

I have trouble understanding this question. I have no idea where to start. Let $A$ be the set of palindromes over $\{a, b\}$. Suppose you are trying to prove that $A$ is not regular using the ...
0
votes
0answers
47 views

Does there exist a regular expression for a series of points?

If I was looking for a certain "shape" or "pattern" in a simple line chart is there a way to describe the series of points that would make up this "shape"? Example: If I had a line chart and I was ...
0
votes
1answer
94 views

Which of the following sets are regular and which are not? Give justification.

Which of the following sets are regular and which are not? Give justification. a) $\{a^nb^{2m}\mid n\ge 0\text{ and }m\ge 0\}$ b) $\{a^nb^m\mid n\ne m\}$ c) $L((a^*b)^*a^*)$ d) $\{a^nb^nc^n\mid n\ge ...
0
votes
2answers
47 views

Regular expresson a's and b's

Need to construct a regular expression that recognizes the following language of strings over the alphabet {a,b}: - The set of all strings over alphabet {a,b} in which every occurrence of b is ...
0
votes
0answers
40 views

Regex - Ternary number that leaves a remainder of 3 when divided by 4

I need to find the regular expression behind: L = {α ∈ {0, 1, 2}∗ | α leaves a remainder of 3 when divided by 4 and is a ternary number} Any help would be greatly appreciated!