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
2answers
23 views

Prove that L is a sub-language of the CFG G by using induction. (CFG,Induction,School)

i am asking for help with a question from a course in Logic im reading at university. I am aware that this type of question is frequently asked here(i have looked at alot of other questions/answers) ...
0
votes
1answer
9 views

Find the language of a given grammar

I have the following grammar: S ⇒ Aa A ⇒ B B ⇒ Aa I need to find the language of this grammar but I am having trouble. I have never had to make a language out of a grammar that has no end state so ...
1
vote
1answer
24 views

Is the following language context-free?

I need to show whether the language $L_2$ is context-free or not where $L_2$= $\overline{L}$ such that L= { $a^nb^m$ : 0 ≤ n ≤ m ≤ 2n }. I am able to show that L is context-free , S­> aSb | aSbb | ε, ...
-2
votes
2answers
20 views

Construct a turing machine that accepts L = {ww : w belongs to {a,b}*} [closed]

Construct a Turing machine that accepts $L = \{ww : w \in \{a,b\}^*\}$?
2
votes
0answers
30 views

Difference of a regular language and a context-free language

I know that given the context-free language L and the regular language R, the language L \ R is context free. But what about R \ L ? My attempt is as follows: R \ L = R $\cap$ $\overline{L}$ We ...
0
votes
0answers
25 views

Language generated by context free grammar

I studied about CFG and one point confused my mind. If rules of grammar given like that; $S \to AB\ |\ C$ then continue with rules of $A$, $B$, $C$ or other nonterminals. Should we define $L(G)$ ...
0
votes
1answer
43 views

Give a NFA over the alphabet {a ,b , c}

How do I solve this? Give a NFA over the alphabet {a, b, c} whose words have a length which is multiple of 4 or are such that the number of a’a plus the number of b’s in the word is even. Use then ...
-2
votes
2answers
63 views

Why to define alphabet as a set?

In formal languages, alphabet is the set of all symbols used to form words in our language. Why is the notion of "set" used in this definition, instead of some other kind of collection, e.g. class? ...
9
votes
4answers
510 views

What's the point of allowing only quantification of variables in first-order logic.

In first-order languages, ${\forall}$ is allowed to quantify only over variables, so that ${\forall}v(P)$, where $v$ is some variable and $P$ is a WFF is the only kind of a WFF concering universal ...
2
votes
1answer
32 views

How does ZFC solve the problem of alphabet in formal languages?

(In case someone thinks this is another question about the seeming circularity in formal languages and is going to downvote because of this, it's really not; don't downvote yet, keep reading) Perhaps ...
0
votes
1answer
27 views

Are there any rules concerning the variable symbols in first-order languages?

I have read that one part of alphabet in first-order languages is an infinite collection of variables. Are there any rules about what the symbols of these variables should look like? One can often ...
1
vote
1answer
38 views

Does the size, direction, etc. of symbols make them different if the meaning is the same?

Does the direction/size of a symbol matter if we are writing down the alphabet for a formal language? What I mean is, we have two formulas, $a<b$ and $b>a$. In that case, is $<$ a different ...
0
votes
2answers
39 views

Do we have to write down definitional abbreviations when writing the alphabet for a formal language?

If we want to have new symbols in our language, which are definitional abbreviations for strings of symbols already in our language's alphabet, do we have to add them to that alphabet? For example, ...
2
votes
1answer
70 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
46 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
25 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
37 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
21 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
32 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
26 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
24 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 ...
1
vote
1answer
26 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: ...
0
votes
1answer
42 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
167 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
65 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
31 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
31 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
44 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
22 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
54 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, ...
1
vote
0answers
27 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
46 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
45 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
24 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
8 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$. ...
2
votes
1answer
31 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
51 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
271 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
33 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
30 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
18 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
42 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
34 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.