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
0answers
13 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 ...
0
votes
0answers
38 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
34 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
13 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
10 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
35 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
18 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
27 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
27 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
14 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
14 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
32 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
35 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
46 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
56 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
20 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
51 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
33 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
28 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
19 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
22 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
17 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
28 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
0
votes
2answers
35 views

If language L is not regular, and L ⊂ M. Do we know if M is regular or not?

I have been given some questions to do regarding regular/irregular languages. And have the following questions True/False (i) If L is not regular and L ⊂ M, then M is not regular. (ii) If L ⊂ M and ...
1
vote
1answer
39 views

{w| w ∈ {a, b} * is not a palindrome} Prove this language is not regular. [duplicate]

I've been doing some work to prove some languages are not regular. I have previously used pumping lemma to prove by contradiction. However I am used to questions which ask to prove languages such as ...
2
votes
2answers
31 views

prove the complement of a language is context free

Language $L=\{a^n b^n c^n : n\geq1\}$ is not context free and it is known (please correct me if I am wrong). What i would like to know is will the complement of this language be a context free, if ...
0
votes
3answers
40 views

How can I prove this language is not regular?

$$\left\{a^{2^n}\mid n \ge 0\right\} \subset \{a\}^*$$ How can I prove this language is not regular?
2
votes
1answer
56 views

Zermelo–Fraenkel Set Theory

So I'll try keeping this real short and simple. Assume that language $L$ is defined as $\{ x\in \{0,1\}^* \}$ (finite binary strings) such that $x$ encodes a proof in ZFC that 4 is a prime number. I ...
0
votes
0answers
7 views

How to determine if I should use top-down or bottom-up parsing for a given formal language?

Let's say I have created a simple language with some grammar rules. Now I need to implement a parser. How to decide what parser shoould I use for a language?
0
votes
2answers
47 views

Help with semi-formal logic

How do I write semi-formally 'there are only 2 objects in the universe'? My hypothesis is: ∃x∃y(x≠y) Any ideas?
0
votes
2answers
56 views

Let $\Sigma = \{a, b\}$. Does $\varepsilon \in \Sigma^*$?

I know it's really basic question but here it is: Does the null word $\varepsilon$ belongs to the set of all words of an alphabet $\Sigma$? For example, Let $\Sigma = \{a, b\}$. Does $\varepsilon ...
0
votes
0answers
53 views

Formal Languages and Automata proof

$L$ and $K$ are subsets of $A^*$ where $A$ is an alphabet. Prove that $(L^* K^* )^* = (L \bigcup K)^*$ where $L^*=(L^0)\bigcup (L^1)\bigcup (L^2)\bigcup \ldots$ and ...
0
votes
0answers
14 views

Expressing conditional role inclusions in Description Logic

Given the following concepts and roles: Concepts = {car, IC-engine, electric-engine, gasoline, diesel} Roles = {engine-type, fuel-type} I would like to impose the following axiom for role inclusion: ...
1
vote
1answer
51 views

How to prove that a language `L` is not a regular language?

Given the following question: Prove that the following language is not a regular language: A language L in alphabet $\Sigma = \{a, b\}$ where every word ...
2
votes
0answers
29 views

Size of automata or regular expressions avoiding cross patterns

Let $\Sigma$ be an alphabet of finite size $k$, and $n$ some integer. I am interested in the language of words of size $n$ that do not contain $abab$ as a subword, for any pair $(a,b) \in \Sigma$ (I ...
0
votes
0answers
15 views

find an algorithm to find terminal string [duplicate]

I would like to know an algorithm which, given a cfg, finds those variables A that derives atleast one terminal string. I can show it by giving some production rules and say that particular variable ...
0
votes
0answers
25 views

how to state which words the right congruence class contains.

I would like to know what words does a right congruence class contains given a condition. ie., if there is a class [ab], then the words that come under this class are string with any number of a's and ...
0
votes
2answers
55 views

How to prove Kleene star to be uncounably infinite?

Hi I have a language $L = \{a, b\}$. How can I prove that the Kleene star (set of all words over the language) of this language is uncountably infinite or countably infinite?
0
votes
2answers
24 views

How to show if a language is infinite, then there is no upper bound on the length of words in L?

L is a language over a finite alphabet. How to show that if L is infinite, then there is no upper bound on the length of the words within L? Can someone help me prove this.
3
votes
0answers
77 views

Intuition for the choice of background (set) theory

Problem From the formalist point of view, any mathematical statement should ultimately be an assertion about the derivability of a certain formula in a certain formal system, call it the background ...
0
votes
1answer
30 views

How do I generate regular expression from this deterministic finite state automaton?

I want to create a regular expression from the following deterministic finite automaton: "abb" substring search How do I generate regexp from above dfa and what are the steps for doing so? ...
0
votes
1answer
46 views

Question about formal languages, quotient operator L1/L2.

I come across this problem: Consider the following regular languages: L1={a*b*c*} over the alphabet A={a,b,c} L2={( a b | b b | a )*} the alphabet is the same as above. Find the shortest strings ...
4
votes
2answers
55 views

If $L$ is regular, must the language $L_1 = \{w : w^Rw \in L\}$ be regular, or may it be non-regular?

The reverse, $w^{R}$, of a string $w = w_1w_2...w_n$ is the string $w_n...w_2w_1$. Suppose that L is a regular language. Must the language $L_1 = \{w : w^Rw \in L\}$ be regular, or may it be ...
1
vote
1answer
20 views

Give an example of a language whose Myhill-Nerode equivalence relation is such that if $x,y \in \Sigma^*$ with $x \neq y$, then $[x] \neq [y]$

Suppose $\Sigma = \{0,1\}$. Provide an example of a language $L \subseteq \Sigma^*$ with the property that its associated Myhill-Nerode equivalence relation, $R_L$, is such that every one of its ...
0
votes
1answer
27 views

Push Down Automata that recognizes language

I'm struggling on how to use the stack for this push down automata problem. The problem is to design a PDA that recognizes the language: $$A = \{a^ib^{2i}|\,i>0\}$$ So, we will be pushing a's onto ...
0
votes
2answers
64 views

Designing a deterministic finite automata

How would I go about designing a deterministic finite automata to recognize the language L = {λ, ab, abab, ababab, . . . } consisting of strings that start with ‘a’, end with ‘b’, and alternate in ...
0
votes
1answer
48 views

Deterministic finite automata [closed]

For this question about Deterministic finite automata: Is this answer: bbbb, bbba, bbab, bbaa, b, a correct?
3
votes
1answer
137 views

Challenge on Some Language and PDA

Suppose We have Some language as follows: $L_1=\{w^* | w=x \text{ and } x \in \Sigma^*\}$ $L_2=\{ww^R ww^R | w \in ( \Sigma + \Sigma)^*\}$ $L_3=\{w | w=xy, x,y \in \Sigma^*, y \text{ is a ...
0
votes
3answers
200 views

Prove that the set of palindromes are not regular languages using the pumping lemma.

Firstly I pick a language $xyz$ where $x = \epsilon$, $y = (abb)^{k}$, $z = (bba)^{k}$ where $|y| \ge$ the number of states in the automaton representing my language. Then $xyz = (abb)^k(bba)^k$ is a ...
2
votes
0answers
127 views

The congruence $\{(a^m, a^{m+r})\}^\#$ on $a^+$.

I've spent a bit too long on this exercise. It's time to ask for help. This is Exercise 1.20 of Howie's Fundamentals of Semigroup Theory. Let $\rho_{m, r}$ (for $m, r\ge 1$) be the congruence ...