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

Can we build a DFA less than 5 state for word length 4( 1100)? [on hold]

========================================================== 1 if possible kindly, help me with this question.
0
votes
2answers
20 views

Closure set of closure set intersection - formal languages

Can we say... Given L1 and L2. Is the following true? $$ L_{1}^{*} \cap L_{2}^{*} = (L_{1}^{*} \cap L_{2}^{*})^{*} $$ I think it is true but I can't be sure. What permutation of either wouldn't be ...
0
votes
1answer
30 views

Is there a notation for “Bounded Kleene star”?

I understand that Kleene star is defined as: $$V^*=\bigcup_{i = 0 }^\infty V_i = V_0 \cup V_1 \cup V_2 \cup V_3 \cup \ldots.$$ (given $V$ is a formal language, $V_0 = \{\varepsilon\}$, and $V_k$ is ...
0
votes
1answer
13 views

Lambda and concatenation of languages.

new to math exchange but i'll give this a shot. I'm working with formal languages here, specifically with concatenation. Concatenation is defined as: ...
2
votes
1answer
30 views

Show that there is such an algorithm

Let $L_P = \{+, \geq; 0, 1\} $. The first-order theory of $\mathbb{N}$ in the language $L = L_P \cup \{exp_2\}$, where $exp_2$ the function which sends a natural number $n$ to $2^n$, is decidable. ...
1
vote
0answers
33 views

How can a structure for a formal language be defined? [duplicate]

I'm learning some stuff about formal languages and structures for them. However there's this thing I don't understand. How can we ever define/specify a structure for a language, if we do not yet have ...
0
votes
1answer
51 views

Why does this equivalence stand?

I am reading the proof of the following theorem: THEOREM A. Let $R$ be an integral domain of characteristic zero; then the diophantine problem for $R[T]$ with coefficients in ...
2
votes
2answers
197 views

Why is there a $p\in \mathbb{N}$ such that $mr - p < \frac{1}{10}$?

I am reading the following part of the paper of Denef : Let $R$ be a commutative ring with unity and let $D(x_1,\dots , x_n)$ be a relation in $R$. We say that $D (x_1,\dots , x_n)$ is diophantine ...
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 ...
1
vote
0answers
23 views

Proof that Deterministic Context-free languages (DCFL) is closed under complementation

I'm reading the book Introduction to the Theory of Computation by Micheal Sipser, and is confused with the proof of Theorem 2.42 that the class of Deterministic Context-free languages (DCFL) is closed ...
0
votes
0answers
15 views

Why $H_{V^* \cup W^*} > H_{V \cup W}$ if $H_V$ denotes entropy of language

Let $W \subseteq X^*$ be an infinite language over a finite alphabet $X$, and define ($|w|$ denotes the length of $w \in W$) $$ H_W := \limsup_{n\to \infty} \frac{\log_{|X|} | \{ w \in w \in W, |w| = ...
0
votes
0answers
24 views

Inequality for the set of factors of length $n$ of some regular language

If $W \subseteq X^*$ is some language denote by $$T(W) := \{ u \in X^* : \mbox{there exists }x, y \mbox{ such that } xuy \in W \}$$ the set of factors (infixes) of $W$. If $W$ is regular, then ...
2
votes
2answers
28 views

Set of all factors of regular language regular?

If $L$ is a regular language (i.e. acceptable by a finite automata), is the the set of its factors (infixes) also regular?
0
votes
0answers
24 views

Relation between number coding in shortlex order for 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 ...
7
votes
1answer
292 views
+400

$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 existential theory ...
-1
votes
1answer
94 views

Math replacing natural language [closed]

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 ...
9
votes
1answer
391 views

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
1answer
31 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
32 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
84 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
22 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 = ...
2
votes
1answer
37 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
164 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
95 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$ ...
2
votes
1answer
35 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
34 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
27 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
24 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
11 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
29 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
22 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
64 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
43 views

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

Context: Thanks in advance for any answers
1
vote
1answer
19 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
28 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
38 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 ...
4
votes
1answer
76 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
37 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
70 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
92 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
58 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 ...