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

Find CFG for language

I'm trying to find CFG of language where $L = \{ a^x b^y a^z \}$ where x,y,z = 1 2 3.. .and y = 2x + 2z I have no idea, I'm completely stuck. Any help would be very appreciated thank you
1
vote
3answers
52 views

Deriving contradiction from $a\Leftrightarrow\neg a$

Recently I've been trying to prove some things by strictly following deduction rules. I've been trying to derive incononsistency from unrestricted comprehension axiom via Russell's paradox. I have ...
2
votes
3answers
31 views

propositional language. don't understand the definition?

I'm taking a mathematical logic class, and I don't understand this definition of the $propositional$ $language$, as given by my book: "The propositional language $\mathscr{L}_0$ is the smallest set ...
1
vote
2answers
55 views

Definability and the Separation and Replacement Axiom Schemata

I am beginning to study Set Theory, so naturally one might begin with the axioms. When reading the schemata of separation and replacement, my initial thought was, "Why would we need separation if we ...
0
votes
2answers
16 views

Regular Expression Similarity Check

I was solving Formal Language and Automata Theory for a competitive exam, whence I came upon this following question: The regular expression 0*(10*)* denotes same set as: 0(0+10)* (0+1)10(0+1) ...
0
votes
0answers
35 views

Number of states of a finite automaton recognizing all words beginning with some fixed string $x$

For a string $x \in \{a,b\}^\ast$ with $|x| = n$, how many states are required for an FA accepting the language of all strings in $\{a,b\}$ that begin with $x$? For each of these states, describe the ...
-2
votes
2answers
54 views

Induction Proof - Regular Expressions and Languages

Find an example of languages $L_1$ and $L_2$, where neither $L_1$ nor $L_2$ are subsets of each other, but $$L_1^* \cup L_2^* = \left(L_1 \cup L_2\right)^*$$ Prove Correctness.
0
votes
1answer
39 views

Basic Question about ambiguity of Grammar

I saw one book in Computation Course. I take a picture from this book, and in this book say why (or not) the following grammar is ambiguous? I couldn't find any solution to prove it's ambiguous. ...
0
votes
0answers
30 views

Smallest grammar problem on a single character.

Let the alphabet be $\Sigma = \{a\}$. Say $s = a^6 = aaa aaa$. If the repeated variable $A = aa$ appears $k$ times in the expanded starting rule of a smallest grammar $G_s$ for $s$. Then that ...
1
vote
1answer
38 views

PDA and Some language Grammar inference

L1={$w^* $| w=x and $ x \in \Sigma^*$} L2={$ww^R ww^R $| $ w \in ( \Sigma + \Sigma)^*$} L3={$w | w=xy, x,y \in \Sigma^*$, y is a substring of x} a) there is a PDA(push down automata) that accept ...
0
votes
3answers
47 views

recursive definition odd length strings

Given the alphabet {aaa bbb}, give a recursive definition for the language that only contains odd length strings. must be constructive definition we are suppose to treat aaa as one letter and bbb as ...
1
vote
1answer
63 views

Countable Set & Formal Grammar

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. I try to summarize my though. I think the following proposition is true. suppose $\Sigma$ is arbitrary ...
1
vote
1answer
55 views

Why is the Kleene star of a null set is an empty string?

The articles and textbooks mention that, $\emptyset^\star = \{\epsilon\}$ The star operation puts together any number of strings from the language to get a string in the result. If the language ...
-1
votes
0answers
19 views

The max number of repeats of substrings of a sample of a language.

So we suspect that finding the smallest grammar of strings in the language $\{a^n : n \in \Bbb{N}\}$, is hard. But luckily as far as applications to natural language processing, we would rarely ...
2
votes
1answer
60 views

Challenge on Property of Complement in Language

We have: and M be a finite automata. Suppose d(M) be a deterministic automata that equivalence to M. if $M_1$ and $M_2$ be two finite automata, $M_1 + M_2$ is the finite automata such that the ...
4
votes
2answers
101 views

What's the difference between a logic, an internal logic (language) of a category, an internal logic of a topos and a type theory?

maybe this question doesn't make sense at all. I don't know exactly the meaning of all these concepts, except the internal language of a topos (and searching on the literature is not helping at all). ...
1
vote
1answer
23 views

Can Type 0 grammar generate Type $1,2,3$ languages? [closed]

Can Type $0$ grammar generate Type $1,2,3$ languages? And can Type $1$ grammar generate Type $2,3$ languages? I am confused with the Chomsky hierarchy.
0
votes
0answers
26 views

Design an finite automata for 010 and 01? [duplicate]

I have tried below question for designing automata but didn't success . ...
0
votes
1answer
36 views

Programming string in math

It seems that everything in programming is relatated to some math theory even regular expressions, but what about strings. Is there simple "thing" in math that can be equivalent of a string in ...
0
votes
1answer
31 views

Formulating the Twin Prime Conjecture as a Language Recognition problem.

I'm trying to figure out how to formulate the Twin Prime Conjecture as a language recognition problem. I've got: A = {p: p is the largest prime such that p + 2 is prime} B = {p: p and p+2 are both ...
0
votes
0answers
12 views

What are the classes in A.N. Maslov hierarchy of indexed languages corresponding to Chomsky Hierachy?

As we know,that classes in A.N. Maslov hierarchy of indexed languages of level 2 is in sensitive languages of Chomsky hierarchy. What are the classes in A.N. Maslov hierarchy of indexed languages ...
0
votes
0answers
20 views

Do automatons and formal grammars belong to formal systems

A formal system consists of a formal language, a formal grammar that generates the language, a set of axioms, and a set of inference rules. Are automatons also formal systems? Is an automaton ...
0
votes
1answer
29 views

finding right quotient of languages

Can someone enumerate in detail, steps to find right quotient of languages ie L1/L2. Using an examle will be great. Having a hard time to understand the same.
0
votes
1answer
38 views

What are the differences between a collation and a rule of formation?

I'm a beginner in mathematical logic, and currently studying(myself, without any colleague, which is sad and so asking in here) basics of formal system. Before asking a question, I'll introduce my ...
0
votes
3answers
43 views

Formal Notation - A simple example

I'm taking Formal Languages and Automata Theory course and i couldn't understand the notation below. Can someone explain me this please? $\{ d \mid d \in \{ b f \mid b, f \in \{ a, c, e \} \} \}$
0
votes
1answer
55 views

How do I define a string in formal language by means of a definition of tuple?

I'm constructing mathematical notions and definition from the bottom of the mathematical structure. So whenever I learn, or encounter new concepts, I try to define it step by step, without using any ...
3
votes
2answers
34 views

Is my proof of 2 languages equality correct?

I started to self-study the formal languages theory, and tried to solve the following problem: Problem Prove, that these 2 languages are equivalent: $$ \Sigma = \{a,b,c\}\\ L_1 = \{(abc)^na | n \ge ...
-1
votes
1answer
24 views

Context Free-Language [closed]

Is it true that if L1 are CFLs and L1 subset of L subset of L2, then L must be context-free? if not true, give a counterexample. Otherwise, explain intuitively why
4
votes
2answers
93 views

Mathematical concept for formal languages

A formal language is defined as a subset of finite-length strings over an alphabet. It is similar to the mathematical concept "relation", but the lengths of its strings are not fixed. Since the name ...
0
votes
0answers
15 views

Is this set $L$-distinguishable $M = \{a^i b^k a^j \mid i\#k\#j\}$? Why (not)?

Is set $M$ $L$-distinguishable? Why (not)? Here $L$ is the language that accepts the $bababaa$ string, so $L = \{a,b\}^*\{bababaa\}\{a,b\}^*$, and $M = \{a^i b^k a^j \mid i\#k\#j\}$. Please would ...
0
votes
1answer
22 views

w such that contains at most two 1s, CFG idea

this is my first time that I did a CFG and I ask if it's correct or not. My idea is the follow: A -> 0A | 1B B -> 0B | 1C C -> 0C As the CFG has to ...
0
votes
0answers
34 views

Pumping lemma for $a^n b^{2n}$

I have this question and i am not sure and trying to solve in both way that is through diagram and expression: Question : Prove that $a^nb^{2n}$ is not regular. contradiction: ...
1
vote
1answer
41 views

How to get all permutations of a variable-length word

I need to find all permutations of a set of letters (word) with following parameters: Word lengths $\ell = [1, 20]$ Alphabet $A = \{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t\} \Rightarrow \lvert ...
1
vote
1answer
55 views

Context free grammar $L=\{a^ib^jc^k|j=i+k-2\}$

$L=\{a^ib^jc^k|j=i+k-2\}$ This expression surprise me a lot and put me into deep thinking. what i am doing by solving the expressions: ...
1
vote
1answer
38 views

Deterministic Push-Down Automata

Does there exist Deterministic Push-Down Automata for the language below. Any kind of answer will be highly appreciated! $$L =ba^nb^n U bba^nb^{2n}$$
1
vote
0answers
42 views

Proving irregularity using Myhill-Nerode theorem

I'm trying to prove that the following language is irregular using the Myhill-Nerode theorem $$ L = \{ w\space\epsilon \{a,b,c\}^* | \#_b(w) > (\#_a(w) + \#_c(w))! \} $$ While it's completely ...
1
vote
2answers
94 views

pumping lemma: ww^R not regular

I'm trying to prove that $L = \{ww^R : w \in \{a,b\}^*\}$ ($w^R$ is the reverse of $w$) is not regular using the pumping lemma. Let $p$ be the pumping length and $s = a^pbba^p$. $x = \epsilon$, $y = ...
2
votes
0answers
15 views

Collapsing adjacent states in a grammar

I am trying to write a program which can induce a grammar from an example of the code(really more of a corpus than an example). I'm ignoring the decision problem, because I am doing two things that ...
0
votes
0answers
44 views

Describe the language generated by the grammar $G = \{\Sigma, \Delta\ S, I \} $

I need to describe the language generated by the grammar $G = \{\Sigma, \Delta\ S, I \} $, where $$\Sigma=\{0,1\epsilon \}, \Delta = \{S,X,Y,Z\}$$ and $$I = \{S \to0X|1Y, x \to1Y|1Z, Y \to0X|0Z, Z ...
1
vote
1answer
32 views

Checking my CFG to CNF answer

I attempted to transform the given CFG into CNF. $$S → ASA|A$$ $$A→aa|ε$$ Here are my steps: $$S→X$$ $$X→XA|AX|A$$ $$A→aa$$ $$S→X$$ $$X→XA|AX|YY$$ $$A→YY$$ $$Y→a$$ $$S→XA|AX|YY$$ ...
0
votes
1answer
29 views

Find the language of $\sum^*$

For the alphabet $\sum = \{0,1\}$, let $A,B,C \subseteq \sum^*$ be the languages below. $i. A = \{1, 0, 00, 11, 000, 111, 0000, 1111\}$ $ii. B = \{w \in \sum^*|||w|| \ge 2 \}$ $ii. C = \{w \in ...
0
votes
1answer
23 views

Grammar extraction using pre-existing grammars.

Given a set of strings $s_1, \dots, s_n$ over $\Sigma$ it isn't clear what a good generalization of the strings would be using a regular language, that extends the set infinitely. This comes from the ...
0
votes
1answer
23 views

Proof the 1 language is contained in another

Does anyone know what the best method is to prove that the intersection of Language1 and Language 2 = Language1? Where both languages are over alphabet {a,b,c}.
0
votes
0answers
28 views

Proof by Induction on two languages [duplicate]

I have a question that states - Using proof by induction, prove formally that L(R*) = L((R*)*) -- Where R is a regular expression over a non-empty alphabet. I have am struggling to relate it back to ...
1
vote
1answer
298 views

induction proof for kleene star

i am going through some past exam paper questions on regular languages for some revision, and i am having a bit of trouble with converting general ideas into formal mathematical proofs. the question ...
0
votes
0answers
25 views

CFG Convertion to GNF

I have a very simple CFG that I am trying to convert into GNF. The CFG is: S -> aSbS S -> epsilon I looked at the CFG and I think I can just do the ...
0
votes
1answer
18 views

Which is true about this NFA?

Let $M$ be an NFA with alphabet {0,1} that accepts every binary string. Which of the following is true? a) Every state of $M$ must be an accept state b) $M$ does not have any accept state c) The ...
0
votes
1answer
33 views

Backus-Naur Form with automata

Parsers & compilers usually utilize deterministic finite automata to parse input. It's very easy to implement a generic DFA tool, that simulates any DFA table for example to validate input. ...
0
votes
1answer
45 views

Determine the languages for the given alphabet

For the alphabet $\sum = \{0,1\}, let A,B,C \subseteq \sum^*$ be the languages below. $i. A = \{1, 0, 00, 11, 000, 111, 0000, 1111\}$ $ii. B = \{w \in \sum^*|||w|| \ge 2 \}$ $ii. C = \{w \in ...
2
votes
0answers
43 views

Maths, esp. Godel, and poetry

At the risk of being an interloper: I'm a poet with a bit of mathematical training. Right now I've got a grant from the Arts Council of Northern Ireland to write a collection (loosely) based on the ...