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
2answers
16 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
9 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
15 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
13 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
22 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
1answer
29 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
32 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
25 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 ...
-2
votes
0answers
27 views

Prove language is not regular with pumping lemma [on hold]

$$\{a^n b^m \mid n\neq m\}$$ I can't get my head around pumping lemma method.
0
votes
3answers
36 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
54 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?
-1
votes
0answers
21 views

Mathematical linguistic - help [closed]

At university I have exercises like that one but I don't actually get what is going on here. Could anyone help me undestand this including questions?: 1.How to get first and follow sets(especially ...
0
votes
2answers
44 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
53 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
51 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
48 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
26 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
24 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
52 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
23 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
76 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
25 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
36 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
53 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
19 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
26 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
62 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
47 views

Deterministic finite automata [closed]

For this question about Deterministic finite automata: Is this answer: bbbb, bbba, bbab, bbaa, b, a correct?
7
votes
1answer
131 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
155 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
125 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 ...
0
votes
1answer
49 views

How to prove a language is decidable

I would like to see some proofs to show if particular string in machine M which dfa is decidable or not. I am trying to find some results on this but those are not appropriate. Any examples or proofs ...
1
vote
1answer
46 views

equivalence class for language in Theory of automata

we say x,y is equivalent to language L, if for any $z \in L$ we have: $xz \in L \Longleftrightarrow yz \in L$. for $ L= (ab \cup aab)^* $, what is the equivalence class for L? my professor ...
1
vote
0answers
39 views

Prove that if $L$ is regular, then $\mathcal{L}(L)$ must be regular

Let $\Sigma_n = \{0, 1, ... , n-1\}$. Suppose $L \subseteq$ $\Sigma^*_n$, and let $\mathcal{L}(L) = \{ x \in L : x \text{ is the lexicographically largest among all strings of length } |x| \text{ ...
-2
votes
1answer
36 views

CFG with reverse strings

I've been trying to figure this out for a while, and I'm at a total loss: Write a context-free grammar that generates the language $\{x y\ |\ x$ is a string over $\{a,b,c\},\ y$ is a reverse of ...
2
votes
2answers
28 views

Prove that a regular language $L$ exists satisfying $L_1 \subseteq L \subseteq L_2$ and $L - L_1$ and $L_2 - L$ are both infinite.

Let $L_1, L_2$ be regular languages, with $L_1 \subseteq L_2$ and $L_2 - L_1$ infinite. Prove that a regular language $L$ exists satisfying $L_1 \subseteq L \subseteq L_2$ and $L - L_1$ and $L_2 - L$ ...
0
votes
0answers
34 views

contradiction of pumping lemma on even palidrome language's completion

I have the language of all the words that are not even length palindromes, or more formally: $L= \{ w: \forall u\in\Sigma^*, w\ne uu^r \}$. And I need to prove that the Pumping Lemma for regular ...
0
votes
1answer
38 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
60 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
65 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
66 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
21 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
37 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
55 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
0answers
31 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
56 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
4answers
61 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 ...