# 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 generated them.

1,367 questions
21 views

### Make the language of First Order Logic uncountable

The question is in regards to The Lowenheim-Skolem theorem and the question asks to give a set of sentences that is only true in an uncountable domain. My teacher told me to solve this by "relaxing" ...
21 views

### is there a linear bounded automaton the decides $A_{nfa}$?

first post here :) I was wondering, since regular languages are context sensitive, and since linear bounded automatons can act as an acceptors for context sensitive language, is it possible or is ...
9 views

### Show that no Büchi Automaton with less than 3 states exists for the LTL formula $G(p_1\rightarrow XFp_2)$

Given the LTL formula $G(p_1\rightarrow XFp_2)$, show that there is no Büchi-automaton which recognizes the same set of $\omega$-words $\alpha \in (\{0,1\}^2)^\omega$ with less than three states....
27 views

### How would the Regular Expression (01*)* expand into a set? [closed]

What does the regular expression $(01^*)^*$ expand to a set? I think it would be something like: {λ, 01, 011, 0111, ... , 00, 010, 0110, 0101, ... } If so, can you explain why this is? I am not ...
21 views

### The formal language $L$ is regular iff there is a “reduced” NFA

I would appreciate some help for the following exercise: $L$ is a regular language if and only if there is a "reduced" NFA $N=\langle Q,A,\Delta, q_0,F\rangle$ with $L=L(N)$. With reduced I mean ...
77 views

### Variables and Language

I've been thinking lately about the kind of language we use when doing math involving variables. Consider a typical variable defining statement: "Let x = 2." If we try to parse this statement ...
25 views

### What is the closure property in this case

There is requirements specification which has certain Completeness properties: No "To be done" phrases No references to non-existing items No missing items No missing functions No missing products ...
14 views