Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
26 views

Give a regular expression for $A = \{1^{k}y|k \geq 1, y \in \{0,1\}^{*}$ and $y$ contains at least $k$ $1$'s $\}$

The regular expression that is given is $1(0 \cup 1)^{*}10^{*}$. I'm having trouble realizing why this regular expression describes the language given. For example, the string (for $k$ = 4) $1111$ ...
0
votes
1answer
23 views

Regular Expression Reading

I'm trying to figure out what this regular expression reads as. The regular expression is the following: (0(1 + 2) * 00*) (+ = union) (* = zero or many). I believe this reads as: 0 concatenated ...
0
votes
0answers
41 views

Which is a regular expression for the language?

Could you give me a regular expression for the language that contains at least once the substring $aba$ and at least once the substring $bab$?
1
vote
1answer
39 views

Pumping Lemma Squares Proof Explanation

I'm looking for some help understand this perfect squares proof using the pumping lemma. Here is the proof: I don't understand how n^2 + k < n^2 + n towards the end of the proof. Would anyone ...
0
votes
1answer
46 views

Expressions for $(AB)^R$, $(A \cap B)^R$, $(A \cup B)^R$

For any language A, let $A^R$ be $\{x^R \mid x \in A\}$. Then, for arbitrary languages $A$ and $B$, explicitly write down the expressions for $(AB)^R$, $(A \cap B)^R$, $(A \cup B)^R$. I am not really ...
0
votes
2answers
339 views

Regular expression and DFA/NFA questions

If a language L is generated by a regular expression, then L is recognized by a DFA. I think this is true, because regular expressions describe regular languages, those of which are exactly ...
1
vote
1answer
35 views

Is the language L regular?

Could you tell me if the language $L=\{a^ib^j:i+j=k, k \geq 2 \}$ is regular? Do I have to find a regular expression for this language? Or what can I do to check if $L$ is regular or not?
-1
votes
1answer
45 views

Finding the wrong regular expression

Which one of the following regular expressions does not define the language of all strings that ends with a. $(a + b)^*a$ $b^*aa^*(bb^*aa^*)^*$ $[a(ba)^* + b(ab)^*](a + b)^*a$ $(b + aa^*b)^*a(a + ...
0
votes
1answer
62 views

find a regular expression for a given language

It is given that $\Sigma=\{1,2,4,5,7,9\}$ and $L=\{w: w \in \Sigma^{*} \text{ ,w gets divided completely by }5\}$. Could you help me to find a regular expression for this language?
0
votes
1answer
554 views

regular expression that dont have both substrings bba and abb

All the words that dont have both the substrings bba and abb ‘words that do not have both substrings…’ means that words may have one or the other - just not both (i.e. not abba or bbaabb). I tried ...
3
votes
5answers
82 views

Expression for a bounded function

I have a bounded function, $$ y= \begin{cases} 1 & \text{if $x>1$} \\ x & \text{if $0\leq x\leq 1$}\\ 0 &\text{if $x < 0$} \end{cases} $$ Does anyone ...
2
votes
2answers
47 views

Regular Expression Notation

I'm doing a theory of computation course and can't for the life of me find any good resource that will tell me how a regular expression such as (a+b)* converts to set form. I've thought of a binary ...
0
votes
1answer
76 views

Finding regular expressions

I'm given the DFA shown below and need to find regular expressions for the following languages: $L_{1,2}^0, L_{2,1}^6, L_{2,5}^4, L_{2,3}^5, L_{1,3}^5$. The language $L_{p,q}^r$ is defined as ...
0
votes
1answer
32 views

Is this a regular language? Number of a's greater than $k$

Prove/disprove: $L = \{ w \mid |w|_a \geq 2k \}$, where $\Sigma = \{ a,b\}$ and $k$ is a constant, is a regular language. Intuitively I am saying yes, it is a regular language. But I don't ...
1
vote
1answer
130 views

Check if a regex is ambiguous

I wonder if there is a way to check the ambiguity of a regular expression automatically. A regex is considered ambiguous if there is an string which can be matched by more that one ways from the ...
0
votes
0answers
25 views

Is the next expression true: $(L_1 \cap L_2 )L_3\subseteq L_1L_3\cap L_2 L_3$?

Let $L_1,L_2,L_3$ be languages, Is the next expression true: $(L_1 \cap L_2 )L_3\subseteq L_1L_3\cap L_2 L_3$? After a half an hour of trying to disprove it, I've decided my intuition might be wrong. ...
0
votes
0answers
25 views

productions with identical right hand sides for different nonterminals

Can a regular grammar contain two productions with identical right hand sides? I know in context free grammars shift reduce parsers issue reduce reduce conflicts when smth like this happens. What are ...
2
votes
1answer
65 views

Build regular expression from language

I have the following language: L = {w $\in$ {a,b}* | aa is not part of w}. I have to construct a regular grammar from this language and I thought about first finding the regular expression from the ...
1
vote
2answers
718 views

How can concatenating empty sets (languages) result in a set containing empty string?

In the book "Introduction to the Theory of Computation" by Michael Sipser, in the section 1.3 Regular Expressions: The symbol ε represents the emty string, which may be a valid element of a language: ...
0
votes
1answer
52 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
1answer
38 views

Prove equivalence of two regular expressions.

I am wondering if there is a standard way to prove that two regular expressions are equivalent. I have tried to prove, given two regular expressions $r$ and $s$, that $L(r) \subseteq L(s)$ and $L(s) ...
0
votes
0answers
33 views

How to write a Regular Expression

I have seen that the regular expression for the set of strings beginning with a and ending with b is written as a(a+b)*b Can some one tell me how to write this
0
votes
1answer
53 views

Which strings belong to the regular set represented by the regular expression (1∗01∗0)?

I know the string should be like 1…101…10, but not sure how to describe it. Can anyone help me?
1
vote
1answer
64 views

Complement of a Set of Strings in a Language

Suppose $B= \{ 0^n1^m2^{n-m}:\, n\ge m\ge 0 \}$ Is the complement $\overline B = \{ 0^n1^m:\, 0\le n\lt m\}$? Or is it the universe of all possible strings (including all strings with symbols ...
0
votes
1answer
67 views

Proving Equivalence of DFA and NFA

Im trying to learn Equivalence of DFA and NFA.The problem is that in the below explanation Q' is given as the power set of Q.But this statement seems to be contradictory to the previous statement ...
0
votes
1answer
56 views

Find Regular Grammar from NFA

I'm currently doing some self study to improve my half-forgotten college theory of comp skills. I'm going over some problems from an old book and it asks you to find a regular grammar for the ...
0
votes
1answer
648 views

Build regular grammar from regular expression

Is there an algorithm for creating a regular grammar directly from a regular expression? All the discussions and notes I found so far go through an intermediary step of creating an FA for the reg ex ...
2
votes
0answers
189 views

Regular Expression For Set of Strings Not Containing OOO

The following is my attempt at coming up with a regular expression for the set of binary strings that do not contain $000$: $(1 + 01 + 001)^*(\epsilon + 0 + 00)$ I'm going to need it for a ...
-1
votes
2answers
89 views

Deterministic Finite Automata with finite strings

How could I prove that every language with a finite number of strings is the language of some DFA?
0
votes
1answer
351 views

Set of Binary Strings Corresponding To a Regular Expression

$(1 + 01)^*(0 + 01)^*$ I'm thinking {set of all binary strings} $-$ {set of binary strings that begin with 00 and contain 11} Would this be correct?
1
vote
1answer
37 views

Regular Expression that accepts a language L

Given, $L=\{ x \in\{0,\,1\}^* | x=0^n1^m \text{ and }n+m\text{ is a multiple of }3\}$ give a regexp that accepts the language. My thoughts are: $(000)^*(\epsilon + 001 + 011)(111)^*$ Is this right? ...
0
votes
1answer
171 views

induction to prove regualr 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
0answers
397 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 ...
1
vote
1answer
55 views

About described DFA

I need to find DFA (or NFA, $\epsilon$-NFA, it's not improtant (I know how to convert between them)) that accept all strings of $0$'s and $1$'s such that every block of five consecutive symbols ...
1
vote
1answer
42 views

Myhill-Nerode Theorem with constraint

I am trying to to understand the Myhill-Nerode Theorem with the example. $L = \{{0^i1^j}|\ j > i\}$ I have read some article but still cannot fully understand,what I know about is that I have to ...
0
votes
1answer
72 views

Prove/Disprove: $vwvw=vvww$ iff $\{v\}^*\{w\}^*=\{vw\}^*$

Let $\Sigma$ be an alphabet and $v,w\in \Sigma^*$. I'm trying to prove that: $$vwvw=vvww\quad\text{iff}\quad\{v\}^*\{w\}^*=\{vw\}^*.$$ I tried to do it by induction, with no success. Any help will ...
0
votes
1answer
38 views

Mathematical expression of largest $k$ numbers from $n$ numbers $(n>k)$

Can someone provide me a Mathematical expression of largest $k$ numbers from $n$ numbers $(n>k)$ eg $S$ is a 3x3 matrix with [6 8 5 ; 3 4 6 ; 9 0 5] where $n$ = 9 (elements) and I need to ...
1
vote
1answer
109 views

Translate a regular grammar to a regular expression

I want to translate the following grammar into a regular expression: Set of variables V := {S,T} Set of terminals Σ := {a,b} Set of relations S → "" S → aS S → bT T → ...
0
votes
1answer
178 views

Construction of Regular Expression

I have the problem of needing to construct a regular expression corresponding to the set of strings of 0's and 1's whose number of 0's is divisible by five and whose number of 1's is even. ...
2
votes
1answer
58 views

Regular expression for language

Let's have a language $L=\{\omega\in\{a,b,c\}^* | \omega $ contains $ab$ and does not contain $ba\}$ make a regular expression for this language. I've ended up with this one ...
0
votes
2answers
44 views

Concatenation of strings

We have two strings A and B. We have to find if for some n,m A concatenated n times equals B concatenated m times or not. I have made an interesting observation but am unable to prove it.It appears ...
1
vote
1answer
82 views

Question about Regular Expressions, DFA and relations

I have a few questions about discrete math, I can't fully grasp these concepts. For regular expression, what does the U symbol mean, at first I thought it meant that it was similar to or, for example ...
0
votes
2answers
88 views

Proving that a regular expression belongs to a certain language

I've often come by questions that require proving that a certain regular expression belongs to that language. Example: Given $\Sigma = \{0,1\}$, and the language $L$ of all the words that have ...
1
vote
2answers
146 views

Translate from logical formula to regular expression

I want to translate this formula in a regular expression: Explanation: The alphabet is : $\{a, b, c\}$ $w(p) = a$ , means on the position $p$ in the word stands an $a$. For the regular ...
1
vote
1answer
207 views

Proving that $L= \{a^nb^n, n\ge 0\}$ is not a regular language.

The questions i'm 'stuck' on is: Let $\Sigma = \{0,1,2\}$ be the alphabet, and let $L$ be the collection of all the languages that contains only words that have even length. Prove that there are ...
1
vote
1answer
31 views

Regular languages that are stutter-invariant but not star-free (LTL/FO-definable)

I am looking for simple examples and/or general ideas on regular languages (I am interested in finite words and infinite words alike) that are stutter-invariant (a language $L$ over an alphabet $A$ is ...
0
votes
0answers
57 views

Regular expression of: $\{ w \in \Sigma^* : w \text{ does not contain the substring 110} \}$.

Given $\Sigma = \{ 0,1,2 \}$, write a regular expression for $$\{ w \in \Sigma^* : w \text{ does not contain the substring 110} \}\;.$$ I know how to do a regular expression for a language that does ...
5
votes
1answer
651 views

Freshening up on discrete math (regular expressions)

I'm trying to freshen myself up on discrete math( I forgot a lot). I know this is a trivial question and not worth your time. But I forgot how to solve problems involving formal language theory. For ...
0
votes
1answer
306 views

What can be defined as a Regular Set

I'm currently studying compilers and am having some issues with understanding regular sets. For example, lets say I had a set of binary strings, (0, 1). Would all integers that are even and positive ...
1
vote
2answers
53 views

Is $\{w \in \Sigma ^* : |w|_2 mod 4 = 2\}$ a regular language?

Given alphabet $\Sigma = \{1,2,3\}$, is $\{w \in \Sigma^* : |w|_2 \bmod 4 = 2\}$ a regular language? I tried so hard on finding a regular expression but couldn't...