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

-1
votes
0answers
37 views
0
votes
1answer
45 views

Herband model for a forumla

I need to find a Herband model for the formula $Pc \land \forall x (\exists y (Px \leftrightarrow \neg Py))$, where $c$ is a constant and $P$ is a unary relation. I've already read the theory but ...
1
vote
1answer
29 views

What does it mean to say that an automaton construction is “effective”?

Let $L, K \subseteq X^{\ast}$ be languages, then we set $$ K^{-1}L := \{ u \in X^{\ast} \mid vu \in L \mbox{ for some } v \in K \} = \bigcup_{v\in K} v^{-1}L $$ with $u^{-1}L := \{ w \in X^{...
0
votes
1answer
21 views

Which of the following string have two or more parse trees?

Consider the following ambiguous grammar: $S→A|BC$ $A→aAC|B$ $C→bCc|c$ $B→aBb|\in$ Which of the following string have two or more parse trees? $aaabbbbbcc$ $aaabb$ $aabb$ None of these My ...
3
votes
1answer
47 views

Identify inherently ambiguous languages

Which of the following languages is/are inherently ambiguous languages? $L_1=\{a^nb^nc^m|m,n\geq0\}\cup\{a^nc^c|n\geq0\}$ $L_2=\{a^nb^nc^m|m,n\geq0\}\cup\{c^mb^na^n|m,n\geq0\}$ My attempt: A ...
0
votes
0answers
14 views

Find the classes of $L_1=\{w|n_a(w)|n_b(w)=n_c(w)\}$ and $L_2=\{wxw^R|w,x\in(0,1)\}$

$L_1=\{w|n_a(w)|n_b(w)=n_c(w)\}$ $L_2=\{wxw^R|w,x\in(0,1)\}$ My attempt: $L_2$ seems regular since it's finite. $L_1$ is DCFL since we can identify strings of $L_1$ using single stack, first we ...
0
votes
0answers
15 views

What is union of $L_1=\{ww^Rw^R|w\in(0,1)^*\} \space \space \text{and}\space \space L_2=\{a^nb^{n^2}|n\geq0\}$

$L=L_1^+\cup L_2^*$ Where, $L_1=\{ww^Rw^R|w\in(0,1)^*\} \space \space \text{and}\space \space L_2=\{a^nb^{n^2}|n\geq0\}$ My attempt: $L=L_1^+\cup L_2^*$ $L=(CSL)^+\cup (CSL)^*=CSL \cup CSL =...
0
votes
1answer
23 views

Subset of regular language $a^*$

Given $L\subseteq a^*$, then $L$ is definitely decidable $L$ is definitely Turing – recognizable $L$ may not be Turing – recognizable. $L$ is regular My attempt: $L$ may not be regular, ...
0
votes
0answers
26 views

Translate common language to formally

I am learning sentence logic( again) and I have an exercise which I'm not sure If I did it wrong or right: Let $(A,\leq)$ be an totally ordered set. Translate to formal language: "Any totally ordered ...
0
votes
1answer
45 views

Regular language or not?

Let $L$ be a regular language over the alphabet $A=\{0, 1\}$. Is it true that the language of strings $0^n$, where binary representation of n $\in L$, is regular?
0
votes
0answers
8 views

Prove that for any PDA there is another PDA that accepts exactly the same language bu has only one POP state.

Prove that for any PDA there is another PDA that accepts exactly the same language but has only one POP state. My attempt: Let the counter example $L=\{wcw^R|w\in(a,b)^*\}$ and string of $L$ is $...
0
votes
1answer
11 views

Possible strings of Kleene star of $L = \{a^nb^n|n≥1\}$

Consider the following CFL. $L = \{a^nb^n|n≥1\}$ Then which of the following string can be accepted by the kleene star of the language. $aaabbb$ $aabbaaabbab$ $abbaab$ $λ$ My attempt: The ...
0
votes
1answer
13 views

Find the classes of given languages?

Consider the following statements $L_1 = \{wxw^R \mid w∈(a,b)^*, x∈c\}$ $L_2 = \{wy \mid w,y∈(a,b)^*\}$ $L_3 = \{zwz \mid w∈(a,b)^*,z∈\{a\}\}$ $L_4 = \{wxw \mid w∈(a,b)^*,x∈\{c\}^*\}$ Find the ...
0
votes
1answer
15 views

Is given statement decidable or undecidable?

A given non-terminal A in a given grammar CFG is ever used in the generation of word.-Decidable/undecidable? My attempt: It should be decidable problem, We can solve this problem using membership ...
0
votes
1answer
9 views

Find a Context-Free Grammar for this Context-Free Language

$$ L = \{w_1w_2 : w_1, w_2\, \in \, \{a,b\}^*, w_1 \ne w_2\} $$ So far I have produced this grammar which will produce a string of odd length which follows that $w_1$ and $w_2$ wouldn't be equal. $$ S ...
0
votes
1answer
16 views

Prove/disprove that language of complement of $L=\{a^mb^n|m\neq n \space, m,n\geq1\}$ is context free over alphabet $\{a,b\}$?

Prove/disprove that language of complement of $L=\{a^mb^n|m\neq n \space, m,n\geq1\}$ is context free over alphabet $\{a,b\}$? My attempt : Using pumping lemma $L=\{a^mb^n|m\neq n \space, m,n\...
1
vote
0answers
16 views

If $G$ is $LL(k)$, then $L(G)$ is a deterministic context free language.

In formal language theory, a context-free language (CFL) is a language generated by some context-free grammar (CFG). For every grammar, If the correct production can be deduced from the partially ...
1
vote
1answer
23 views

Consider the language $L_1=\{a^pb^qc^r \mid p,q,r>0\}$ and $L_2=\{a^pb^qc^r \mid p,q,r\geq0 \space\text{and}\space p=r\}$

Consider the language $L_1=\{a^pb^qc^r \mid p,q,r>0\}$ and $L_2=\{a^pb^qc^r \mid p,q,r\geq0 \space\text{and}\space p=r\}$, then which of the following statements are true? $L_1\cup L_2$ is a ...
0
votes
2answers
28 views

Context-Free Grammars: How to understand substitution rules

I am at a bit of a loss when it comes to understanding how to apply substitution rules for checking if a string is accepted / rejected for a given context-free grammar (CFG). Suppose I have been ...
1
vote
1answer
21 views

For formal languages $U,V \subseteq X^{\ast}$, what is $\min(U\cdot V)$

Let $L$ be some language, and consider the operator $$ \min(L) := \{ u \in L \mid \mbox{no proper prefix of $u$ is in $L$} \} $$ where a word $u$ is called a prefix of $w$ if it is an initial segment ...
1
vote
0answers
36 views

Turing Machine make use of another Turing Machine

I am expected to formally construct a deterministic TM to compute a function. I already have a TM for $f(x)$. How can I make use it formally while constructing $g(x)$? $g(x)$ is like in the followig ...
-1
votes
1answer
22 views

CFG and Automata regular language and dFA questions

I have the following CFG questions which I am having a hard time getting my head around, I don't have any answers for them so I have no way of knowing if ive done them right or not (even though im ...
0
votes
1answer
26 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
15 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
173 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
77 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
69 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? (I'm ...
1
vote
0answers
33 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 ...
0
votes
1answer
29 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 ones....
0
votes
1answer
22 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
56 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
14 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
29 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
29 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
41 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
35 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
68 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
525 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
36 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
30 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
72 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
49 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
32 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
39 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 ...