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

Context Free Grammar and some details [closed]

Why this grammar shows a Context Free and Linear Language, (i.e, not context sensitive or non-context free). S -> SBA | a BA -> AB aA -> aaB B -> b
3
votes
2answers
61 views

Is the language “substrings of an even-lengthed regular language” also regular?

I want to prove that for a regular language $L$ where $\forall w \in L$ the length of $w$ is even, the language containing the first halves of the words of $L$ and the language containing the second ...
0
votes
1answer
30 views

Regular Expression of alternative 0's and 1's?

Let $L$ be the language of $0$'s and $1$'s in alternate positions, where $$ L = \{ \epsilon, 0, 1, 01, 10, 01010,\ldots\}. $$ Is $(0)*$ + $(1)*$ a valid regular expression that represents this ...
1
vote
1answer
29 views

How to match this language with variables?

How can i go about representing this language in variables? (a) The language of all strings containing exactly two 0's. (b) The language of all strings containing 010 as a substring. My Approach: ...
2
votes
1answer
27 views

Concatenation of context free language and a maybe pointless theorem

In our lecture our professor claimed this result: Let $\{1,\dots,k\}$ be an alphabet (or terminals) for the context free grammar $\tau$, $L(\tau)$ is the language generated by $\tau$. Let ...
0
votes
1answer
114 views

Finite language proof involving finite automata

Question: Show that every finite language (including the empty language) is accepted by some finite automaton with exactly one final state How would I go about solving this? I tried my own approach ...
1
vote
1answer
105 views

Solving the conjugacy equation $xy=yx$ in the free monoid

I'm having some trouble on showing this: Let $\sum$ be a finite alphabet, $x,\ y \in \sum^{*}$. Show: $$(xy=yx) \iff \exists s \in \sum^{*} ,\ i,j \in \mathbb{N}, (x = s^{i}, y = s^{j})$$ If we ...
0
votes
1answer
36 views

Give context-free grammars for these languages(Need clarification for my answer)

I'm just looking to understand if my justification I wrote makes sense (it might not) in a) b). Note: I'm doing exercises from a textbook which has no solutions I can see. So I can't check my answer ...
5
votes
1answer
35 views

Formal Grammar generating $0^p$

Exercise: Find the formal grammar generating the language ${0^p}$ in the binary alphabet for $p$ prime. I have absolutely no clue where to start, nothing of the 'usual' construction strategies seem ...
0
votes
1answer
25 views

Closure properties between 2 languages of different types

Whenever said - The intersection between a Context Free Language and a Regular Language is always Context Free, what is the best logical way to confirm the statement? I have this Chomsky hierarchy in ...
2
votes
1answer
20 views

Concatenation of regular languages.

The concatenation of $L_1$ and $L_2$ denoted by $L_1.L_2$ = $\{uv|u\in L_1\,and\,v\in L_2\}$. If, $$L_1=\{a^n|n\geq0\}\,and\,L_2=\{b^n|n\geq0\}$$ Then why is $$L_1.L_2\neq \{a^nb^n|n\geq0\}$$ I am ...
0
votes
1answer
26 views

Lambda Calculus Reduction (applicative vs normal order)

I am a little confused to reduce these lambda calculus expressions. I am instructed to give applicative and normal order reductions for these expressions. (a) (λx. ((λy.(* 2 y)) (+ x y)))y (b) (λx. ...
4
votes
0answers
69 views

Vague predicates in standard predicate logic [closed]

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: ...
0
votes
2answers
89 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
41 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
1answer
41 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 ...
0
votes
1answer
53 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
40 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
56 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
82 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
26 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
78 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
1answer
27 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
81 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
125 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
75 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.
0
votes
0answers
37 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
52 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 ...
0
votes
2answers
128 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
104 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
76 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
315 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
153 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
80 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
75 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
70 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
58 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
48 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
22 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
12 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
42 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
24 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
30 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
30 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
24 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
24 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
47 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
120 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
68 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
94 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$ ...