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
251 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
45 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
38 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
55 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
27 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
21 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
18 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
34 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
70 views

Pumping lemma-regular language

Show that the language L={ww:w $\epsilon$ {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 are ...
0
votes
1answer
37 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
82 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
104 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
58 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
50 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
47 views

Expressiveness of finite memory programs

Assume we have a simple programming language with while, if, := (assignment), ...
2
votes
0answers
374 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
251 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
28 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
30 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
45 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
29 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
45 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
36 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
49 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
84 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
10 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
27 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
52 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 ...
0
votes
0answers
44 views

“Whether the intersection of two regular languages is infinite” decidable or undecidable?

Could someone explain the below problem? "Whether the intersection of two regular languages is infinite" decidable or undecidable ? Regards Avisingh05
0
votes
0answers
18 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
22 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
58 views

Binary regular language?

Given $m,n∈Z$, $A=\{a,b,c\}$ is a finite alphabet set ,and $L=\{(a^m,a^n)\}^*$ is subset of $A^*\times A^*$ . Is this binary language $L$ regular over $A(2,\$)$ ( i.e.$\{A∪\{\$\}\}\times ...
0
votes
0answers
41 views

Regular language?

Is the binary language $L=\{(a^2,a)\}^*=\{(a^2,a),(a^4,a^2),(a^6,a^3)...\}$(a subset of $A^*\times A^*$,with $A=\{a,b,c\}$ a finite alphabet set) is regular over $\{A∪\{\$\}\}\times ...
0
votes
0answers
17 views

Shortest trace for LTL

Given a finite trace semantics for LTL (one where u,i |= X phi does not hold if i = |u|) is there a better bound of the length of a minimal trace for a satisfiable formula ? By better, I mean better ...
0
votes
0answers
99 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 ...