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
1answer
77 views

How to formalize a variable-binding operator, such like $\frac{d}{dx}$?

How to formalize a variable-binding operator, such like $\frac{d}{dx}f(x)$? For instance, I think we should treat $\frac{d}{dx}$ as a higher-order function of $x$, returning a function that takes it ...
1
vote
1answer
59 views

Decidable and Recognizable

I'm trying to work on this problem but I cant seem to find an approach to it: For any language L ⊆ Σ∗ define the language PREFIX(L) := {w ∈ Σ∗ | some prefix of w is in L} (a) Show that if L is ...
1
vote
1answer
37 views

Finding the language of a finite automaton

Is there any formal and elegant way of finding the language of a finite automaton? For example, It's trivial that the language accepted by the following diagram of the automaton $A$ is $L(A) = (a ...
1
vote
1answer
40 views

Is the union of undecidable languages not Turing-recognizable?

The question is as follows: Let us define $$L := \{w \mbox{ | either }w = 1x \mbox{ for some } x \mbox{ ∈ $A_{TM}$ or } \mbox{$w$ = 0$y$ for some $y$ ∈ $\overline {A_{TM}}$}\}.$$Prove that neither $...
1
vote
0answers
32 views

Is there a concept of distance between number of steps needed to move from one step to another?

Let's say that we have a set of rewrite rules: $$AB \mapsto AC, A \mapsto B, B \mapsto A$$ Given the two strings $ABC$ and $BCC$ we know we can rewrite $$ABC \mapsto ACC \mapsto BCC$$ We can ...
1
vote
0answers
22 views

turing machine decidable description for the language

L = { | R is a regular expression that produces at least one word in {a, b} * which contains a symbol exactly 3 times} ...
0
votes
1answer
38 views

turing machine decidability language

I must show that this language is decidable but I think it's not {D, Ρ} | D is a DFA and P is a ΡDA which L(D) ∩ L(Ρ) = ∅ } Here what I think I give a reduction from E(TM). I suppose that this ...
0
votes
1answer
28 views

How to disprove the following using negation?

Let $\mathcal{F}=\{f|f:\mathbb{N}\to\mathbb{R}^+\}$ Disprove $\forall f,g\in\mathcal{F}:$$\log{f(n)} \in O(g(n)) \implies f(n) \in O(3^{g(n)}).$ (Here we assume log has base 2) (We disprove) Let $\...
0
votes
0answers
11 views

Metamathematic: Cover the case if X=Y

I want to formalize: "If X is less than Y, Then U is equal to Y ", and have been told that $$ \bf [\forall V \sim X=(Y+V)]U=Y $$ does not cover the case X=Y. Therefore I have rewritten it as $$ \bf [\...
2
votes
1answer
25 views

Proving that everything in a language can be generated by a grammar

Suppose $L=\{w \in {a,b}^* \colon \#b(w) = \#a(w) \}$, the language of all strings with an equal number of occurrences of $a$ and $b$ in all possible arrangements. Furthermore, this language can be ...
2
votes
1answer
32 views

Determine string is even length with regular expression

There is a set of strings of even length over $\{k,l,m\}$ that contain exactly one $k$. And I try to write its regular expression. I think it can be in that format: ...
1
vote
1answer
55 views

Regular expression of the set of strings of even length

I should try to write a regular expression of the set of strings of even length over $\{k,l,m\}$ that contain exactly one $k$. If string has even length, and if we have one $k$; there should be (odd ...
1
vote
1answer
168 views

Regular expressions represents the sets provided

While I am studying formal languages, I see these questions.What are the answers for them? a) The set of strings over {a, b, c} that begin with a, contain exactly two b’s, and end with cc. b) The ...
2
votes
1answer
67 views

Why is an alphabet a subset of the set of strings that it generates?

In his An Introduction to Substructural Logics, Restall provides the following definition of the string algebra generated by a set (p. 14): The string algebra generated by a set $X$ is a set $\...
3
votes
1answer
34 views

Existence of context-free grammar over {0,1} alphabet

Is there a context-free grammar $G$ for which $L(G) = \lbrace w \in \lbrace 0,1 \rbrace^{*} : \exists a,b \in \lbrace 0,1 \rbrace^{*} \wedge w = aba \wedge |a| = |b| \rbrace$? This question could be ...
2
votes
1answer
32 views

Context-free language

Given $L= \lbrace w \in \lbrace 0, 1 \rbrace^* \ : \ |w|_0 \leq |w|_1 \leq 2 |w|_0 \rbrace$, where $|w_0|$ is number of zeros in $w$. Is $L$ context-free?
1
vote
1answer
45 views

Construct a regular expression for a given language

I'm currently working on some exercises to get used to create regular expressions from given languages and i'm stuck with a fairly simple exercise. So could you please tell me how to construct it step ...
3
votes
1answer
23 views

Language of binary multiplications relation.

Given $\Sigma = \lbrace 0, 1 \rbrace$ and $L \subseteq (\Sigma \times \Sigma \times \Sigma)^*$. Let $first(w), second(w), third(w)$ be word from $(\Sigma \times \Sigma \times \Sigma)^*$ limited to ...
0
votes
1answer
102 views

Converting right-linear grammar to left-linear grammar

I have the following language: $$L := \{b(ab)^n a^m \mid n, m \geq 0\}$$ and have created a right-linear grammar: Grammar $G(b(ab)^n a^m)$ Terminals $a, b$ Non-terminals $S, S_1, ...
2
votes
0answers
32 views

First-order graph rewritings

Let a rewriting rule be a couple of first-order formulas $\langle \varphi, \psi \rangle$ such that: $\varphi$ has $x_1, \dots, x_i$ free variables, and all atomic formulas contain at least one $x$ ...
1
vote
1answer
12 views

Defining a right-linear grammar for a language

Would someone please be able to confirm if my right-linear grammar is correct for the language L? $L := {b(ab)^na^m | n, m \ge 0}$ Grammar $G(b(ab)^na^m)$ Terminal a,b Non-terminal S, S1, ...
1
vote
1answer
30 views

Using a language to define a grammar

I'm currently having trouble understanding how to use a language to generate a grammar. Using the language: $$L=\{a^n b^m | n, m \geq 1\}$$ as an example: I know (from my notes) that this ...
1
vote
2answers
51 views

Using Pumping Lemma to prove a language not regular

I'm currently stuck on a problem were I'm asked to look at a language and prove whether or not it is a regular language or something else such as context-free. I've been given the example: $$\{...
1
vote
1answer
57 views

How to check if a language is regular

I'm currently studying a formal languages & automate module on my course and I have been asked to answer the following question: Which of the languages below are regular? If the language is ...
0
votes
0answers
30 views

Length of symbols in the alphabet of the Oxford English Dictionary.

Consider an alphabet $A$ comprised of singleton symbols, so for example we might have $A=\{a,b,c,...,z\}$ or even $A=\{0,1\}$ among many others. The length of each symbol in these alphabets is one. ...
5
votes
0answers
11 views

Solving the equation X = AX + B of languages for X [duplicate]

I'm currently working on the following problem for my computer theory class. It goes as follows: Let $A$ and $B$ be regular expressions. Show then that $A^* B$ is the solution of $X = AX + B$. ...
1
vote
1answer
34 views

How to prove that $\forall x\in \Bbb{Q}:\ x\ne 0\implies [\exists a,\ b\in \Bbb{I}: x=a\cdot b]$ if $\Bbb{I}$ is set of irrational numbers?

I initially thought contrapositive would be easier, so I wrote $\forall x\in \Bbb{Q}:\ [\forall a,\ b\in \Bbb{I}: x\ne a\cdot b]$ $\implies x=0$. But I still had no idea how to start. Could someone ...
2
votes
0answers
24 views

How do I get and/or verify a formal Grammar for a given formal Language?

I was given the Language $L=\left \{ a^nb^na^nb^n |n\epsilon \mathbb{N} \right \}$ and I'm supposed to find a Grammar that generates that Language. After some trying and fiddling I found one that I ...
1
vote
1answer
62 views

Is the empty string always in a finite alphabet?

Is the empty string always an element of an aribitrary finite alphabet? I understand that the empty string is part of the Kleene-Star of any alphabet, but is it intrinsically part of any finite ...
12
votes
3answers
281 views

Words built from $\{0,1,2\}$ with restrictions which are not so easy to accomodate.

We assume a ternary alphabet $V=\{0,1,2\}$ and are looking for a generating function describing the number of words of $V^*$ fulfilling certain restrictions. The words I am interested in do not ...
1
vote
1answer
36 views

How to prove $\forall x,y\in\mathbb{R} : x^3+x^2y=y^2+xy \Leftrightarrow y=x^2\lor y=-x?$

Let $x,y\in\mathbb{R}$ Assume $x^3+x^2y=y^2+xy$ Then $x^2(x+y)=y(x+y)$ Then either $(x+y)=0$ or $(x+y)\ne0$ Assume $x+y=0$ Then $y=-x$ Assume $(x+y)\ne0$ Then $y=x^2$ Then $x^3+x^2y=y^2+xy \...
4
votes
1answer
40 views

Identify recursive languages?

Consider the following languages. $L_1 = \{<M> \mid M \text{ takes at least 2016 steps on some input}\}$, $L_2 = \{<M> \mid M \text{ takes at least 2016 steps on all inputs}\}$ and $...
1
vote
2answers
73 views

Help with finding the generating function of this language?

I've simplified this a bit so that I can just get help with the basic steps. Say we have a language of all words over $\{a,b,c,d\}$ where the only letters allowed to commute are $ab$. I need help ...
0
votes
1answer
22 views

What is flaw on my proof to identify any string of $L_2$ using single stack?

Consider the following languages: $L_1=\{a^nb^mc^{n+m}:m,n≥1\}$ $L_2=\{a^nb^nc^{2n}:n≥1\}$ Which one of the following is TRUE? Both $L_1$ and $L_2$ are context-free. $L_1$ is context-free while ...
0
votes
2answers
43 views

Formal languages

Let language $L$ be denoted by the regular expression $a^*b^*$ What is wrong with the following “proof” that $L$ is not regular? Assume that $L$ is regular. Then it must be defined by a DFA with k ...
0
votes
2answers
33 views

formal languages and computability concepts

Prove whether or not language $L$ ={$a^pb^q : p ≥ 100$ and $q ≥ 100$ are fixed integer values, and $i ≥ 0$} is regular. I'm not sure how to prove this.
0
votes
1answer
35 views

Formal languages and Computability

Can someone please tell me how would you start proving this? Thanks Prove whether or not language L = {a^(p+qi) : p and q are fixed integer values, and i ≥ 0} is regular.
0
votes
1answer
25 views

Strong induction on formal language proof

Q: Show that $\sum^* = L_1\sum^*L_2$ if $e\in L_1 \subseteq \sum^*$ and $e\in L_2 \subseteq \sum^*$ for any alphabet $\sum$. In these equivalence proofs, one way is usually easy. I guess it is ...
1
vote
3answers
55 views

Proving two languages are equal

Q: Show that $\{a,b\}^* = \{a\}^*(\{b\}\{a\}^*)^*$. I am aware of the fact that both sides are sets, infinite sets actually. So for example showing that both sides are subsets of each other would be ...
2
votes
2answers
42 views

How to check whether arbitrary finite [syntactic] monoid is aperiodic or not?

Does there exist an algorithm to decide whether a (finite in my case) syntactic monoid is aperiodic or not? By definition, a monoid is aperiodic if for each $x$ from monoid there exists an $n$ with $...
0
votes
1answer
68 views

Prove concatenation of strings is associative

Q: Prove, using the definition of concatenation given in the text, that concatenation of strings is associative. DEFINITION: The concatenation of strings $x$ and $y$, written $x \circ y$, or ...
1
vote
1answer
29 views

How can I interpret a multiply-quantified statement?

∃ x ∈ R such that ∀ y ∈ R, x + y = 0. Can anyone help me rewrite this statement in plain english without symbols or variables? So far I have "There exists a real number whose number and other number ...
0
votes
2answers
18 views

What is the automaton recognising the language generated by G?

Why is B not accepted as an answer?: S --> 0A A --> 0A A --> 1B B --> 1B B --> e Which ends up in the state of the automata is in the accept state.
1
vote
1answer
21 views

What is the Right Context of a Word in Formal Langauge Theory?

I am reading this paper and am unable to understand this notation in section 2.2 - The right context of a word $u$ according to a language $W$ is the language {$u^{-1}w$ | $w \in W$}. The ...
0
votes
2answers
35 views

Is there a language like L in which $\overline {L^*} = \overline L^*$?

Assume that for every language L over the alphabet $\Sigma$, we define $L^*$ , $\overline L$ , $\Sigma^*$ & $L^n$ like this : $L^n$ means joining L to itself n times. For an alphabet like $\...
0
votes
1answer
107 views

Stronger Pumping Lemma for Context Free Languages

Hi Math Stack Exchange, Taking a class in automata theory, and having real trouble proving the following strong automata theorem for context free languages (from Sipser, Problem 2.37): If L is a ...
1
vote
1answer
28 views

How to identify context free language?

Consider the following context-free grammars$:$ $G_1: S → aS|B, B → b|bB$ $G_2: S → aA|bB, A → aA|B|ε, B → bB|ε$ Which one of the following pairs of languages is generated by $G_1$ and $G_2$, ...
0
votes
1answer
43 views

Identify language of given PDA?

Consider the transition diagram of a PDA given below with input alphabet $Σ =\{a,b\}$ and stack alphabet $Γ = \{X,Z\}. Z$ is the initial stack symbol. Let $L$ denote the language accepted by the PDA. ...
0
votes
1answer
54 views

Reduction to/from REC and RE language?

Let $X$ be a recursive language and $Y$ be a recursively enumerable but not recursive language. Let $W$ and $Z$ be two languages such that $\overline{Y}$ reduces to $W$, and $Z$ reduces to $\overline{...
1
vote
1answer
43 views

Subtracting a context-free language from a regular language

I have the language $L=\{a, bb\}^*-\{a^ib^i|i\geq1\}$ and I have to show that $L$ is context-free. The first language is Regular, if I'm not mistaken, and the second is a well known context-free ...