# Questions tagged [formal-languages]

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 grammars and automata which can be used to generate them.

2,005 questions
Filter by
Sorted by
Tagged with
29 views

### Construction of a Finite State Automaton given a grammar

I have been studying formal language and automata theory from Mathematical Methods in Linguistics (Partee et al.). Specifically, I have been learning about finite state automata, formal languages, and ...
1 vote
45 views

### State Diagram in Finite State Machines

This question is in Grimaldi's book: Let $I$ = $o$ = {0, 1}. Construct a state diagram for a finite state machine that recognizes each occurrence of $1010$ in a string x $\in$ $I^*$. (Here overlapping ...
• 63
38 views

### Question about $B^{+}$

This question is in Grimaldi's book: For $\Sigma$ = { x, y, z } , let A,B, $\subseteq$ $\Sigma^*$ be given by A = {xy} and B = {$\lambda$, x}. Note: $\lambda$ is the notation of the empty string. ...
• 63
18 views

### L = { a^n b^m : n != m } - Matrix, Time varying, ordered and programming grammar

I would like help to prepare a thesis that will include: The language chosen, its description, its classification in Chomsky's hierarchy, Matrix grammar generating the language chosen in point 1. Time-...
44 views

### Software language specification: null VS empty objects.

I have noticed that in software language specifications, there is pretty much always a NULL element and I am wondering if it is strictly necessary and how it maps to algebraic structures, given that ...
• 253
186 views

### Why does $\forall n \in \mathbb{N} \vdash P(n)$ not imply $\forall n \in \mathbb{N}P(n)$?

I am trying to understand why $\forall n \in \mathbb{N} \vdash P(n)$ doesn't imply $\forall n \in \mathbb{N}P(n)$ by studying the concepts in this answer, and had 2 questions about the difference ...
• 3,019
1 vote
129 views

### Why do we need a metatheory if we can include self-referencing language in the object theory?

I am wondering why we need to have a metatheory in order to talk about a theory- why can't we just add self-referencing terms to the language of the formal system on which the theory itself is based, ...
• 3,019
83 views

• 251
32 views

84 views

• 121
179 views

• 63
1 vote
31 views

### What's the maximum possible compression ratio for different languages?

Given two alphabets $A=\{a_1, a_2, ..., a_n\}$ and $B=\{b_1, b_2, b_3, ..., b_m\}$, what is the maximum average compression ratio possible to achieve by bijectively encoding strings of B using strings ...
• 1,303
19 views

### Construct the grammar that generates the given languange

Find a grammar that generates this language : L = { w : |w| mod 3 >= |w| mod 2 } over the alphabet sigma = {a} I tried and got the abstract logic . Length where mod 3 < mod 2 is length should be ...
50 views

• 3,468
1 vote
46 views

78 views

### Equivalence relations, formal languages, and hypercube walks - what did I unleash on my students?

I teach a class in discrete mathematics and formal language theory. On my most recent final exam, I asked a question that involved a crossover between equivalence relations and formal languages. Here'...
• 10.5k
1 vote