Formal languages are studied in computer science and linguistics. They are usually defined using various types of grammars (e.g. regular, context-free) and automata (e.g. deterministic and pushdown automata, Turing machines). There is a hierarchy of formal languages, which is based on the type of ...

learn more… | top users | synonyms

2
votes
0answers
31 views

$F[t]$ has undecidable positive existential theory in the language $\{+, \cdot , 0, 1, t\}$

Consider the ring $F[t, t^{-1}]$ (the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$). Theorem 1. Assume that the characteristic of $F$ is zero. Then the existentia theory ...
-1
votes
1answer
89 views

Math replacing natural language [on hold]

Before reading any further. I ask yous to think creatively on this subject. I was in shower and was pondering over A.I. (Strong A.I. both at human level and beyond human level) as I do from time to ...
2
votes
0answers
79 views
+200

Algorithm to answer existential questions - Reduction

Lemma 1. For any $x$ in the ring $F[t,t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$), $x$ is a power of $t$ if and only if $x$ divides $1$ and ...
1
vote
0answers
16 views

Representing numbers by quasilexicographic ordered strings, formula for size of conversion between different alphabets

Let $X_r = \{ 0, 1, \ldots, r-1 \}$ and $X_b = \{ 0, 1, \ldots, b-1 \}$ be two finite alphabets with order's given by their numerical value. Consider the quasilexicographic (or shortlex) order on ...
0
votes
1answer
29 views

Using the Pumping Lemma to show that $\{a^nb^{n^2} : n\in \mathbb{N} \}$ is not a context-free language

Consider the language $L= \left\{a^nb^{n^2} : n\in \mathbb{N}\right\}$. I want to prove that this language is not context-free by using the Pumping-Lemma for context-free languages. So, I picked the ...
2
votes
0answers
65 views

Of strings and substrings: A problem of probability

Problem Let $\Sigma=\{a, b\}$. Let $\Sigma^*$ denote the Kleene star of $\Sigma$: \begin{equation*} \Sigma^* = \{\varepsilon, a, b, aa, ab, ba, bb, aaa, aab, \ldots\} \end{equation*} where ...
0
votes
1answer
20 views

proving a implication with regular expressions

I'm trying to prove the following implication to be false: R*(T+S) $\equiv$ R*(TS) $\implies$ T $\equiv$ S. Proof: We have that IF R*(T+S) $\equiv$ R*(TS) THEN T $\equiv$ S Let R, T = ∅ and S = ...
1
vote
0answers
26 views

Count the number of strings containing $ac$ or $ca$ for a fixed length over ternary alphabet $A = \{a,b,c\}$ using rational series

This question is a continuation the one asked here, and which already received good answers. Here I am asking for a solution using rational series of formal languages as suggested by the user J. E. ...
4
votes
1answer
111 views

The existential theory is undecidable

Lemma 1. For any $x$ in the ring $F[t,t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$), $x$ is a power of $t$ if and only if $x$ divides $1$ and ...
6
votes
2answers
91 views

Describe and count the set of sequences containing $20$ or $02$

Let $X = \{ 0,1,2 \}$ be a ternary alphabet and denote by $X^*$ the set of finite sequences (i.e. strings) with three symbols. For $w \in X^*$ with $n$ the length of $w$ and $w = w_1 w_2 \cdots w_n$ ...
0
votes
1answer
27 views

Length of substring if we just consider a subdivision in $\log n$ substrings

Let $u$ be a string of length $n$ and consider a subdivision in $\log n$ substrings $u = u_1 u_2 \cdots u_{\log n}$. Is it true that there exists a constant $C$ such that for each $1 \le i \le \log n$ ...
1
vote
1answer
30 views

What is the cardinality of a string set with finite alphabet?

We can construct a language $\mathcal L$ with the finite alphabet $\mathcal A $ (e.g. $\{0,1,\dots,9\}$): $$ \mathcal L=\{string|string=x^* \land x\in \mathcal A\} $$ $x^*$ is $x$'s Kleene Closure, ...
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 ...
2
votes
2answers
25 views

Is the language $\{yxzx^Ry^R \mid x,y,z \text{ belongs to } \{0,1\}^+ \} $ regular?

This is a question from Iran's national grad school entrance exam. In the answers key, the answer was that the following language is regular but I doubt it is true, I proved using pumping lemma that ...
0
votes
1answer
21 views

Difficulty understanding the concept of writing an L-System?

I've recently tried my hand at L-Systems, but I'm having some difficulty wrapping my head around it. I watched this video on the subject which is pretty good, but I had a question around the 1:43 ...
0
votes
0answers
22 views

Formally define replacement operation for rules of replacement

I'm having some trouble formally defining non-uniform substitution the replacement operation for a rule of replacement in propositional logic. Based on the idea of "Non-Uniform Substitution" from here ...
0
votes
0answers
10 views

inverse proof of closed under union

I am being posed the following question: given are languages $L_1, L_2, L_3 $ and $ L_4$. $L_1$ is a decidable language and $L_2$ and $L_4$ are both recognizable languages. Considering $L_1 = L_2 ...
2
votes
0answers
27 views

Stuck in a Context-Free Proof

I am trying to work through the pumping lemma for CFLs. $L_1 = \{0^n 1^{mn} : n,m \in \Bbb N\}$ I am trying to find a contradiction. I have currently chosen $z= 0^p1^{2p}$ to be my string. Then ...
0
votes
2answers
28 views

Why is the below language regular?

If I have a language $$L=\left\{wxwy : w,x,y \in \{a,b\}^+ \right\}$$ I am not getting how come we are able to write regular expression for this of the form $$a(a+b)^+ a(a+b) ^+ + b(a+b)^+ b(a+b) ...
0
votes
0answers
14 views

Definition of (minimal) domain?

Consider the following links: http://www.glottopedia.org/index.php/Domain_%28Syntax%29 http://www2.let.uu.nl/uil-ots/lexicon/zoek.pl?lemma=Minimal+domain&lemmacode=542 What kind of mathematical ...
2
votes
1answer
20 views

Union of two languages

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
29 views

pumping lemma for CFL vs pumping lemma for regular languages

Is the pumping lemma for context free languages a generalization of the pumping lemma for regular languages (for instance if we set $u=\epsilon, v=\epsilon$ we can then relate $wx$ in the pumping ...
0
votes
1answer
37 views

Quick question on DFA

I'm asked to list all DFA over the alphabet sigma = {0} such that the set of states is {s0, s1}, for which the initial state is s0 and the set of accept states is either {s0} or {s1}. And also asked ...
0
votes
1answer
40 views

What does P(x) : x = -3 mean?

Context: Thanks in advance for any answers
1
vote
1answer
17 views

Syntactic congruence and Myhill Nerode equivalence

What is the difference between these two demonstrated by a concrete example? I mean I know the definitions of them, and I know that former implies latter, and intuitively I believe this, but I don't ...
3
votes
1answer
26 views

Pumping Lemma for CGF question

I'm going through a pumping lemma for a proof that: the language $B = \{a^nb^nc^n \mid n\ge 0\}$ is not context free The first case considers when both v and y contain only one type of alphabet ...
1
vote
1answer
26 views

Best approach to determine the equivalence classes of a formal language

I created a minimum automaton for a formal language using the Myhill-Nerode theorem. The language for which I created the automaton is defined by $L=\{w \in \{a,b\}^*:w=av \text{ for a word } v ...
0
votes
1answer
18 views

Symbol to write 'for all $x$ that satisfy: $|x-2|\lt c$'

For example in the epsilon delta definition that states: a limit $L$ exists when $x$ approaches $a\iff (\forall \epsilon\gt 0) (\exists\delta\gt 0)$ for all $x$ that satisfy ...
1
vote
1answer
11 views

Closure under splitting?

Say there is a regular language $L\subseteq \lbrace 0,1\rbrace^\ast$ Would the language $L_1 =\lbrace w\in\lbrace 0,1\rbrace^\ast | w0\in L\rbrace $ also be regular? (i.e. $L = L_1\circ\lbrace ...
1
vote
1answer
36 views

In formal languages, why is $L^0 = \{ \epsilon \}$? Why isn't it the empty set ∅?

It just doesn't make logical sense to me that a language to the power of $1$, is itself, but to the power of $0$ is only a tiny part of itself (since every language contains $\epsilon$) Wouldn't it ...
3
votes
1answer
75 views

What is this semi-circular symbol in the middle of a formula?

I have tried every search term I can think of but I can find no way of knowing what this symbol between the (a) and the trP means: Some context here, Point 2 in the third paragraph. Original image ...
0
votes
1answer
35 views

Context-free language or not

It is language: $L = \left\lbrace a^ib^jc^kd^l \mid i+k < j+l+3 \right\rbrace$ Is it context-free or not? I have two versions: 1)Pumping lemma(refute): get a word $uvxyz = aabcd$ if $i=2$ we get ...
0
votes
1answer
64 views

How can I prove this statement about square root?

Introduction In computer science there is a field called Formal Methods and Specifications. In this field software designers design softwares by specifying their functionalities in formal methods, ...
0
votes
1answer
67 views

Transition diagram for DFA's.

I have a homework question that asks to draw the transition diagram for the following: Draw transition diagrams for the DFAs below for the following languages. The alphabet Σ in this example is ...
2
votes
1answer
55 views

Left and Right hand associativity equivalent first order logic

Say we are in a first order theory, and one of our inference rules is the associative rule saying that we can infer $(A \vee B) \vee C$ from $A \vee (B \vee C)$. Using the other logical inference ...
1
vote
0answers
18 views

Showing that language $L^{'}$ is regular given $L$ is regular [duplicate]

Say $L \subseteq \{a,b\}^*$ is a regular language with words whose length is divisible by 3. Each word $w \in L$ has the form $w=xyz$ with $|x|=|y|=|z|$, where $y$ is then called the middle third of ...
1
vote
1answer
67 views

Undecidable definition of pure function

I am trying to come up with a formal definition for functional purity in a simple programming language (think JavaScript). What I've got so far is this: DEFINITION: A statement is impure if ...
0
votes
1answer
29 views

Pumping Lemma for Regular Language (Is my answer correct)?

I've been working on understanding the Pumping Lemma for 2 days now and I feel like I may have finally got somewhere. I was hoping to show you guys a question and my working out and if you think i'm ...
0
votes
1answer
22 views

On the existence of a non-regular language $L$ such that $L^2\in \text{Reg}$?

Is there a non-regular language $L$ such that the language $L^2$ is regular? Nothing comes to my mind. What's your proposition ?
0
votes
1answer
25 views

Showing that calculus are (not) equivalent

Let $\mathcal{A} = \{ x,y \}$ be an alphabet. Consider the following rules for derivation: $R_1 : \begin{array}{c} \hline \epsilon \end{array},\\R_2: \begin{array}{c} z \\\hline zx \end{array},~ R_3: ...
0
votes
0answers
22 views

Check if language is context free

The language is the set of finite prefixes of the infinite word: $a^1b^2a^3b^4 \dotsm$ The question is to show that this language is not context-free. So to my eye, it is not context free, let $p$ ...
1
vote
1answer
26 views

Prove the following language is not regular using pumping lemma.

Prove the following language is not regular using the pummping lemma $L = \{a^{n!} \mid n\geq0, n\in\ \mathbb{N} \}$. What I have done so far is: Assume $L$ is regular. So, there is a $DFA$ for $L$ ...
-1
votes
1answer
80 views

Describe a PDA that accepts the language L = {w | w = a^n b^n c^n , N > 0}

I was wondering could somebody give me an idea on how to answer this. This computation should start with an empty string >q0---->q1. How does the stack be incorporated into this question? sorry, new ...
0
votes
2answers
71 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
1answer
29 views

Graph and language/automaton equivalence

I'm looking for a reference rather than an answer. I think I'm just not Googling the right combination of terms. I imagine that there is a class of graphs which is equivalent to some class of ...
-5
votes
1answer
63 views

Let $A = \left\{{11,00}\right\}$. Find $A^n$ for $n = 0, 1,3$ [closed]

I need to answer this question but I am struggling to understand what I need to do here, any help will be greatly appreciated!
0
votes
2answers
31 views

Examples of undecidable languages contained in 1*?

I've been given the following question Show that there is an undecidable language contained in $1^*$. But I can't think of any undecidable languages that are contained! Can someone please lend a ...
1
vote
1answer
29 views

Pumping Lemma proof and the union/intersection of regular and non-regular languages

I am still learning the pumping lemma. I have a problem for which I used it. I used it on the first part (a) but I am unsure if it is correct. Parts b-d, I am not sure how to do it. I created a dfa ...
0
votes
1answer
21 views

Context Free Grammer (CFG) for a language

Consider the language above $\Sigma = \{a,b,\$\}$: $$L = \left\{ x$y : x,y\in\{a,b\}^* \land \left|x\right| \ne \left|y\right| \right\}$$ I need define a CFG for this language. I've tried couple of ...