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

0
votes
1answer
15 views

Determine whether a language belong to R,RE\R,coRE\R or other

For the following language, determine to which class it belongs $$L_3=\left\{\langle M\rangle\Big\vert|\langle M\rangle|\le 2016\text{ and M is a TM that accepts }\varepsilon \right\}$$ I've ...
-2
votes
0answers
12 views

Formal Specification - discrete math for Stack

I need to define a series of Abstract Data Types (ADT) using discrete mathematics for a Formal Specification. For example, to define Empty of a Set ADT I would do the following ...
3
votes
1answer
59 views

Question about regular languages

Let $L$ be a regular language over the alphabet $A=\{0\}$. Is it true that the language of binary representations of $n$, such that $0^n\in L$ is regular?
2
votes
1answer
69 views

How many words are there in a finite context-free grammar in Chomsky normal form?

Given a CFG $G$ written in CNF with $|V|$ variables and $|T|$ terminals, what's the upper bound of the number of words in $L(G)$ if it is finite? Specifically, the Chomsky normal form requires that ...
0
votes
0answers
5 views

deducting High level program function to type logic

I am trying to construct a model of a function in high level language, like java, using FOL of Z3 ( First Order Logic) ( Typed logic ). Would like to know whether how I should proceed? Have any one ...
3
votes
0answers
67 views

Are all statements about math inherently formal? Can one do math without formal logic? [duplicate]

Are all people who do mathematics applying (whether they know it or not) formal logic? Does every statement someone may make about math, at its core, a formal statement in mathematical logic? ...
1
vote
0answers
32 views

Find $A^n$ for n=0,1, and 3: Languages and Finite State Machines

The question is: Let $A$={11,00}. Find $A^n$ for n=0,1, and 3. Would i be right in thinking that $A^0$ = {λ} $A^1$ = {11,00} $A^3$ = {111111,111100,110011,110000,000011,000000,001100,001111}. if ...
-1
votes
0answers
70 views

Find $A^n$ for n=0,1, and 3: Languages and FSM

I am having trouble trying to work out this finite state machine and languages question. Let $A=\{11,00\}$. Find $A^n$ for $n=0,1, 3$. Where would I begin?
0
votes
1answer
27 views

Is it possible for a subset of a non-context free language to be context-free?

For example, if I have a non-context free language of B, is there such a context free language A such that A is a subset of B? I have been thinking of examples but am unable to think of any valid ...
0
votes
1answer
20 views

accepted language notation for CFG for recurring 1's and 0's

Hi I often have trouble with the notation when having to write the accepted language for a finite automata or CFG. Right know I have a CFG that generates groups of any number of 1's followed by any ...
2
votes
2answers
48 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
13 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
28 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
25 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
1answer
38 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 ...
1
vote
1answer
33 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
49 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
65 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? ...
10
votes
4answers
523 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
34 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
29 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
71 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
47 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
30 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
38 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
36 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 ...
2
votes
1answer
30 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
51 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
32 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
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
70 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
48 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
51 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
26 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
32 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 ...