The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
2answers
53 views

Can one prove that a language is regular without having a regular expression?

I was wondering if one could prove that a language is regular without showing a DFA/NFA or a regular expression that expresses it. For example: $L = \{w \in \Sigma^* : w \text{ has at least two ...
3
votes
1answer
280 views

Notation of cross entropy

I have a question regarding a notation that seems to be very usual. For starters, cross entropy is defined by: \begin{align}H(X, q) &= H(X) + D(p||q) \\ & =-\sum_x p(x)\log_2 q(x)\end{align} ...
1
vote
1answer
54 views

Pumping Lemma for regular languages proof template

http://www.cs.uiuc.edu/class/fa06/cs273/Lectures/pumping-lemma/pumping-lemma.html So, I went to that site and it says: $w = xyz$ $|xy| \leq p$ $|y| \geq 1$ for all $i$, $xy^iz$ is in ...
1
vote
1answer
52 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 ...
1
vote
1answer
59 views

Working with the word w⋅y, while given the word y⋅w

$L$ is a regular language. I am given $F(L)$ such that $$F(L)= \{wy \mid yw\in L\}$$ I need to prove that if $L$ belongs to $L_\text{dfa}$, $F(L)$ also belongs to $L_\text{dfa}$. I am having a hard ...
1
vote
1answer
29 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
1answer
40 views

Pumping lemma proof of $L = \{a^nb^m \mid 0\leq n<m\}$

Prove the following language is not regular using the pummping lemma $L = \{a^nb^m \mid 0\leq n<m\}$ I tried solving this problem what I don't think I was able to reach an accurate proof. But this ...
0
votes
1answer
15 views

Finding a Regular Expression with a Specific Length from a language

Given this language, I was supposed to find the Regular Expression that represented it. Having given up and getting the answer later (below) I couldn't understand the regular expression. Given ...
0
votes
1answer
28 views

Prove a language is Context Free

I am working on the following problem and I do make a little progress. Let me state the question first: Prove that the set of strings consisting of $a$'s and $b$'s with an equal number of $a$'s and ...
0
votes
1answer
28 views

Prove L is not a regular language (A Finite State Automaton cannot accept it)

$$\mathscr L = \{x \in \{0,1\}^* \mid \text{there is a } y \in \{0,1\}^* \text{ such that } x = yy\}$$ How can I prove that this is not a Regular language? I tried using proof by contradiction but ...
0
votes
1answer
114 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 ...
0
votes
1answer
81 views

Pumping lemma-regular language

Show that the language $L = \{w \mid w \in \{a,b\}^{*}\}$ is not regular by using the following version of Pumping Lemma: Let $L$ be the language, which has an infinite number of words, then there ...
0
votes
1answer
46 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
136 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
1answer
134 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. ...
0
votes
1answer
55 views

Confusion related to context free grammar

If G is a context-free grammar such that it has the productions of the form $$ X \rightarrow \alpha Y ,X \rightarrow \alpha $$ How can I show that L(G) is a regular language
4
votes
0answers
66 views

Applying the Myhill-Nerode Theorem

Consider the language $$L=\{x y^{(n)} z y^{(n)} w: x,z,w \in \Sigma^*, y \in \Sigma, z\text{ does not contain }y, n \geq 0 \}.$$ To show that the language is not regular using the Myhill-Nerode ...
2
votes
0answers
52 views

This proof in my textbook involving the pumping lemma appears incorrect - is it?

It states Let $B$ be the language $\{0^n1^n2^n | n \geq 0\}$. We use the pumping lemma to prove that $B$ is not regular. The proof is by contradiction. Assume to the contrary that $B$ is regular. ...
2
votes
0answers
48 views

Expressiveness of finite memory programs

Assume we have a simple programming language with while, if, := (assignment), ...
2
votes
0answers
537 views

Pumping lemma for $a^nb^{2n+1}$

I know how to solve pumping lemma for $a^nb^n:n\geq 0$. But I don't understand how can I solve this example : $a^nb^{2n+1}:n\geq 0$. I tried to solve it but I am not sure that I have solved it ...
2
votes
0answers
279 views

Regular, Context-free, Recursive, Recursively Enumerable Language Relationships

I am currently under the believe that all regular languages are context free, thus all regular languages are recursive, and therefore all regular languages are recursively enumerable. If I am given ...
1
vote
0answers
27 views

Language of Specific Grammar

I ran into this exercise in Sipser's Note on Computation Theory. Consider the following grammar $G$: $$\begin{align} S &\to aSD \;|\; bB \\ D &\to dS \;|\; a \\ B &\to bB \;|\; ...
1
vote
0answers
38 views

Proving irregularity using Myhill-Nerode theorem

I'm trying to prove that the following language is irregular using the Myhill-Nerode theorem $$ L = \{ w\space\epsilon \{a,b,c\}^* | \#_b(w) > (\#_a(w) + \#_c(w))! \} $$ While it's completely ...
1
vote
0answers
38 views

Minimal DFA for a given regular expression

How can I construct a minimal DFA from the following definition? $L=\{w \in \{a,b,c\}^* $: if the second-to-last letter from w is an $a$, then the number of $c$'s $\le 1\}$ I've already made a ...
1
vote
0answers
57 views

Prove the following by using mathematical induction

If we define the alphabet such that $$ \Sigma = {\{a,b}\} $$ and let $w$ be a string over it. I'd like to prove $$ ( \operatorname{comp}(w))^R = \operatorname{comp}(w^R) $$ where $$ w^R$$ and ...
1
vote
0answers
32 views

Why every regular language is in $\text{TIME}(n)$?

How can I prove that every regular language $R$ has linear time complexity, i.e. every regular language satisfies $$R \in \text{TIME}(n)$$
1
vote
0answers
48 views

$DFA/NFA$ for $L(OPPOSITE)=\{uv:vu\in L\}$

I'm trying to prove that: $L(OPPOSITE)=\{uv:vu\in L\} \in L_{FA}$ given that: $L \in L_{FA}$ . I'm trying to construct a finite automata that accepts $L(OPPOSITE)$ in order to prove it but I got ...
1
vote
0answers
36 views

Constructing a Turing decidable machine from DFA

I am a trying to prove that every regular language is decidable. So in order to prove that I am trying to show that I can move from deterministic finite automaton (DFA) to a Turing decidable machine. ...
1
vote
0answers
46 views

Systematic way of creating the complement of a regular grammar?

Regular languages are closed under complement. And any regular language can be generated using a regular grammar. Is there a systematic way to create the rewrite rules for the complement of a regular ...
1
vote
0answers
39 views

Regular Functional Algorithms

A language is regular if it is accepted by a read-only Turing machine. I am curious about applying this model to functional problems rather than decision problems. Definition: A functional read-only ...
1
vote
0answers
54 views

Proving that language is regular or not regular

Let $L$ be a regular language. Prove that: $L_{+--}=\left\{w: \exists_u |u|=2|w| \wedge wu\in L\right\}$ $L_{++-}=\left\{w: \exists_u 2|u|=|w| \wedge wu\in L \right\}$ ...
1
vote
0answers
87 views

Isn't the set of all literature a regular language?

Let one piece of literature be one string. Let's define our alphabet to be sufficient to represent all literature (e.g. we may need a page-turn character, etc). So, since the collection of current ...
0
votes
0answers
11 views

A name for the number system used in versioning software

Software often uses a numbering system where one "digit" increments independently of the others. For instance, the next version of Software 2.9 might be Software 3.0 or Software 2.10 or Software ...
0
votes
0answers
31 views

Pumping lemma for $a^n b^{2n}$

I have this question and i am not sure and trying to solve in both way that is through diagram and expression: Question : Prove that $a^nb^{2n}$ is not regular. contradiction: ...
0
votes
0answers
18 views

Hierarchy of hardness for the pumping lemma for regular languages.

Whenever I bring up the Pumping lemma for regular languages people often say `better to use the Myhill-Nerode theorem'. I want to make this thought rigorous. Def: A language $L$ is pumpable if there ...
0
votes
0answers
31 views

Context-free languages

Is the following language context-free? $\{ w \in \{a,b,c\}^* : (\#_a(w) - \#_b(w)) \cdot \#_c(w) = \#_b(w)$ and all c's are encountered before any a$\}$. $\#_a(w)$ = amount of a's in w Thanks in ...
0
votes
0answers
21 views

reverse of language, decidability

Consider a language L(D) = {w: w and its reverse are in L(D)}. Does reverse of L(D) is the same language ? If so, then consider L = {: M is a DFA for L(D)}, does this make this a turing decidable ...
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
24 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 ...
0
votes
0answers
18 views

How to say “Take result X from the following simultanious calculation and multiply by z” in one equation?

If I have a simulataneious equation, for example: { 5x+10y=3 10x+5y=4 } so the person solving the exuation would need to calculate X and Y (1/3 and 2/15 ...
0
votes
0answers
108 views

Chomsky Normal Form solution for a problem

Here is my attempt at CNF, Original: $$ \begin{align*} S &\to 1 A \mid O B \\ A &\to O B O \mid 1 0 \mid \epsilon \\ B &\to A 1 A \mid 0 1 \end{align*} $$ CNF: $$ \begin{align*} S ...
-2
votes
0answers
37 views

Pumping Lemma & Regular Language

For each regular language L, we have an integer k such that: ...