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

Vague predicates in standard predicate logic [on hold]

I'm trying to work out if a sentence of the form: 'Bob is larger than Maureen and almost as large as Chris' can be adequately formalised in predicate logic. One could just write: ...
2
votes
0answers
58 views

A PDA using only O(log(n)) cells of its stack [on hold]

Are languages corresponded to PDA's that uses only $\log(n)$ cells of their stacks, subsets of deterministic context free languages? Are they closed under intersection, $*$,...?
0
votes
1answer
41 views

Context free grammar for AN

I need to write Context free grammar for describing moves in a game of chess using the Algebric Notation. Can anyone help me get started. f.ex. how do I write this for this move: Bb5 Bd7.
1
vote
1answer
34 views

Difference between $\phi$ anf $\epsilon$ in regular language.

What is the interpretation of both $\emptyset$ and $\epsilon$ in a regular language? Do they both mean empty sets? If so then why is $\emptyset^*=\epsilon$ , $\emptyset^+=\emptyset$ and ...
0
votes
0answers
21 views

Final state of a Finite automaton.

Can a finite automaton not have a final state? For example, for the question "what is the number of states need to accept an empty language?" people answered that one state is enough to accept a ...
1
vote
0answers
14 views

How to prove a language is NP-Complete where L consists of graphs (G,s,t) with a hamiltonian path from s to t [closed]

L = { (G,s,t) | G is a directed graph, a Hamiltonian path exists from s to t, and some path from t to s exists - (not necessarily Hamiltonian path) } How to prove L is NP-Complete ?
0
votes
1answer
50 views

Regular Language Problem?

Let L be the set of all strings that are not in the English language. Is L regular? From textbook, would like some help? Someone recommended to me to think about how regular and regular languages ...
0
votes
1answer
36 views

Proving language as regular

Suppose that A and B are languages such that A o B is regular. Suppose that B is regular. Prove or disprove that A is regular. I am having a tough time with questions relating to proving a language ...
0
votes
2answers
48 views

Proving L is a regular language?

I am having tough with problems like this. Can someone help me. Let L be the set of all strings that are not in the English language. Is L regular?
0
votes
3answers
24 views

What is the difference between language of empty string and empty set language?

I am reading Introduction to Automata theory by Ullman. It says the empty set and set containing empty string is different. I am unable to understand the difference between them as the empty string ...
1
vote
0answers
24 views

When does $A,A\cap B, A\cup B\in S$ imply $B\in S$?

Let $S\subset 2^{\Sigma^*}$ be some family of formal languages over some alphabet $\Sigma$. Consider the the following statement: $A,A\cap B, A\cup B\in S$ implies $B\in S$ For which ...
0
votes
1answer
59 views

Kleene star proof: $(AA)^*$ is the set of strings from $A^*$ of even length

Let $A$ be an alphabet. By $A^{**}$ let us denote the set of all strings from $A^*$ of even length. (This definition may be incorrect but it was given to me in the question) Show that ...
0
votes
0answers
18 views

Construct a grammar that generates this language

This is a homework problem. The problem is: Find a grammar that generates this language: L = {w: |w| mod 3 ≠ |w| mod 2} over alphabet Σ = {a}. The transitions I came up with are: S -> Baa B -> ...
1
vote
2answers
31 views

Find a grammar that generates this palindrome language

This is a homework problem. The problem is: Find a grammar that generates this language: L = {wcw^R: w ∈ {a,b}+ } over alphabet Σ = {a, b, c}. I have tried many different transitions, but can't ...
1
vote
1answer
68 views

Set theory questions about $ϵ$ and concatenation

I have two questions I'm wondering about. Take a look at my answers and tell me if I did anything wrong or any suggestions/hints would be appreciated thanks! Q1 (T/F): Let A be an alphabet, e ...
0
votes
3answers
57 views

Language of prefixes of regular language is regular.

Let $L$ is regular language and $L_1$ be the language of all words whose prefixes are all in $L$. I need hint to prove that $L_1$ is regular.
1
vote
0answers
25 views

If syntax with Backus-Naur form [closed]

I'm doing a "parser" with the BNF syntax. My program should get as input the condition of an "if" statement, where, if the user enters the following condition: ...
0
votes
0answers
34 views

Are my definitions correct? (Formal language)

I will describe how I understand below. Please tell me where I'm thinking wrong or correct. Symbol is an undefined term just like a set. Symbol can be ragarded as a object we consider. ...
1
vote
1answer
47 views

Riesz-Fischer Theorem applications in language?

This is a follow-up of the question I posed here Chomsky, Feynman, Thom I was reading the following comment on Von Neumann (see below) and it occurred to me that what I am asking about Chomsky and ...
2
votes
3answers
270 views

Chomsky, Feynman, Thom

This is a continuation of this question that I asked earlier. I would like to know about the mathematical criterion possibly allowing for a translation of Chomsky's computation into Feynman's view ...
0
votes
2answers
124 views

Convergence and Crash of a derivation (Chomsky)

I would like to pose you a terminological question, regarding the following quotes from Noam Chomsky's work: "A strong feature must be eliminated (almost) immediately upon its introduction into ...
1
vote
1answer
101 views

Is a lanaguage is cfl

I've been asked to decide whether a given language is CFL. If yes, I should find the grammar that creates her, and if not, I need to prove it (with the pumping lemma). The given language is the ...
4
votes
0answers
66 views

Unique factorization in human language? (Kummer rings at stake?)

I keep on bringing some interesting analogies (at least I hope they are) between the study of language by authors such as Zellig Harris or Noam Chomsky and some mathematical issues I have read a bit ...
2
votes
3answers
278 views

Abstract alphabets by Kolmogorov??

As a linguist I sometimes have a hard time trying to figure out the sense in which mathematical concepts are / might be used in my discipline. It is no wonder that we linguists are fascinated by the ...
4
votes
2answers
123 views

Mathematical structures of language (Zellig Harris)

I would like to get some feedback from you regarding the mathematical structures which describe the objects and/or properties described in the paragraph below, which I take from the book Mathematical ...
0
votes
1answer
74 views

Given a set of integers and operators, find if number is obtainable

Let's say I have a set of sequential integers $(x_1,x_2,x_3,x_4,\ldots,x_n)$ and operators $(+,-,\times,/,(,))$ (arithmetic operators and parenthesis). Now say we can have any $t$ numbers from the ...
0
votes
1answer
46 views

Set builder form for representing strings

Is there a way to represent strings or palindromes using set notation? For representing palindrome using set notation, I arrived at this notation $$S=\{ab^{n}c:N\; |\; n \geq 1 \land n \leq 3\}$$ I ...
1
vote
1answer
43 views

Context free grammar to NFA

I've been given an exercise to solve which goes as follows: generate an NFA from the given CFG, S -> AB | c A -> aAb | c B -> bBa | c Now correct me if I'm wrong, but if this language has an NFA it ...
1
vote
1answer
51 views

Proving languages are undecidable

Let L5 be the language { {G,D} | G is a CFG, D is a DFA, and L(D) ⊆ L(G) } Show that L5 is undecidable. Is L5 R.E.? Is it co-R.E.? I am not quite sure where exactly to start with this. Could ...
2
votes
3answers
42 views

regular language proof, a language partial to a regular one

So, I've been trying to solve a question I got and I think I'm correct but I'm not positive. Is the language {w| www belongs to L' and L' is regular} regular? I couldnt find any way to prove it isnt ...
0
votes
0answers
18 views

Nondeterministic final automat - example

Show a possibly nondeterministic FA to accept the following language: $$\left\{w\in\{a,b\}^*:w\text{ contains at least one instance of }aaba,bbb,\text{ or }ababa\right\}$$
0
votes
1answer
11 views

Formal languages problem

What is meant by L1L2 ? Does the n have to be the same for both? So, aabbcc is an element of L1L2 and aabbcccc is not? How about the first problem - Epsilon. Is it an element of L1L2? Since n>0 in L1 ...
0
votes
1answer
37 views

How to prove a language is not an FAD using homomorphism.

Could anyone please let me know with an example on how shall one can prove the language is not a FAD using Homomorphism.
0
votes
2answers
20 views

Language of Grammar

Let $G = (V,T,S,P)$ be the phrase structure grammar with $V = \{0,1,A,S\}$, $T=\{0,1\}$, and a set of productions $P$ consisting of: $S \to 1S$ $S \to 00A$ $A \to 0A$ $A \to 0$ What is the ...
1
vote
2answers
29 views

What does this proposition mean?

$∀x ∈ P(\Bbb{N}), x \notin \{\} \Rightarrow ∃y ∈ x, ∀z ∈ x \ | \ y < z$ Where $P(x)$ is the power set. I'm interpreting it as "in all subsets of the natural numbers, there exists a value smaller ...
0
votes
0answers
28 views

Forming the alphabet of a grammar

What does {nA|A->x element of P} mean when defining an alphabet ? Note that A is subscript
0
votes
1answer
23 views

Designing a Pushdown Automation to accept a language

Im a novice trying to understand the theory of computation.Im trtying to learn about PDA.I understand that it is a machine counterpart of CFG.Im basically referring to Introduction to Automata Theory ...
0
votes
0answers
23 views

Designing a turing Machine belonging to a language

Im trying to learn the concept of turing machines.I have understood the basic stuff like its a simple mathematical model of a computer and its parts.Now im asked to create a turing machine. ...
0
votes
1answer
37 views

Prove language is not context free with pumping lemma

$$L=\big\{a^{3k}b^{2k}c^k\in\{a,b,c\}^* | k>= 0\big\}$$ I'm trying to use the pumping lemma to prove this language is not context free. so far I have... $p=$ Pumping lemma $S = a^{3p}b^{2p}c^p$ ...
0
votes
2answers
51 views

Construct a PDA to accept the language

construct a PDA that accepts the language: a) $L_1 = \{ a^k b^k c^i \mid k,i \ge 0 \}$ my answer is : $$\begin{align*} &S\to AA\\ &A\to abc \mid ab \mid c \mid \lambda \end{align*}$$ b) ...
0
votes
2answers
55 views

How to design a Context-Free Grammar and Pushdown Automaton for the following language:

How would you design a context-free grammar for the following language? $\{p^n \ r^m \ p \ \ b^{m+n} \ \ r^2 ∣ m,n\geq 0\}$ Derive a Pushdown Automaton that accepts the same language as the CFG. ...
2
votes
1answer
69 views

How can a proof by formula induction in a formal language be formalized?

From a set of not-so-rigorous lecture notes on Metalogic: Formulas of $L$: (i) Each sentence letter is a formula. (ii) If $A$ is a formula, then so is $\neg A$. (iii) If $A$ and $B$ ...
1
vote
1answer
22 views

Automata Language regularity proof by construction.

I've been trying to prove or disprove a question that popped during our last session in Uni, we've been using automaton constructing to prove regularity for a while now and I really do have the handle ...
0
votes
0answers
52 views

Is this an accurate description of structures and interpretations.

I read about structures and interpretations today. I've described them below this paragraph. Have I accurately described them? If not, what have I incorrectly described? A structure, $\mathscr{A}$, ...
2
votes
0answers
44 views

Recursive definition of a language

Define recursively the language L of all finite strings over the alphabet Σ={a b} satisfying both criteria: All words in L contain the substring aa an odd number of times. All words in L are such ...
0
votes
2answers
30 views

Context-free and regular language decidability

If L is some context-free language and R is a regular language, I am pretty sure that L ⊆ R is decidable (while R ⊆ L is not) but I am having some difficulty giving an algorithm to prove that it is ...
0
votes
1answer
26 views

How to construct a context free grammar that generate following language. $\{a^nb^nc^k \in \{a,b,c\}^* | n,k >= 0\} $

$$\{a^nb^nc^k \in \{a,b,c\}^* | n,k >= 0\} $$ $E \to aEbS $ $S \to c$ I do not know where to go next, or even if this is right at all?
0
votes
1answer
25 views

is $\{a^n b^m | n \neq m\} $regular or non regular?

$\left\{a^nb^m\mid n \neq m \right\}\subset \{a, b\}$. I have been asked to prove this is irregular but I think it is regular as I can write a regular expression a*b* for it. Am I wrong? If so how ...
0
votes
0answers
18 views

Is the string in $L(G)$?

I have to write an $O(n^3)$ algorithm to determine whether a given string $w=a_1 a_2 \dots a_n $is in $L(G)$, where $G=(N, \Sigma ,P, S)$ is a context-free grammar in Chomsky normal form. Could you ...
0
votes
1answer
33 views

Construct context free grammar which generates following language $\{wcw^R\in\{a, b, c\}^*\mid w\in\{a, b, c\}^* \}$

(i) $\{wcw^R\in\{a, b, c\}^*\mid w\in\{a, b, c\}^* \}$ So far I have $E \to EcE$ $E \to a$ $E \to b$ $E \to c$ But I'm new at this and feel I'm miles away from a finished answer