Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

1
vote
2answers
46 views

Finding Language of a CFG

Say you are given the following CFG $G$: $$ S \to S_1 \mid S_2 \\ S_1 \to AbAS_1c \mid \epsilon \\ S_2 \to BaBS_2c \mid \epsilon \\ A \to Aa \mid \epsilon \\ B \to Bb \mid \epsilon $$ What is $L(G)$? ...
-2
votes
0answers
15 views

How can I get my program to execute correctly? [on hold]

I have to Write a modularized program that will utilize a main menu to control the program’s functions and a list to store the members of your team. The following functions that your program needs to ...
2
votes
1answer
160 views

regular expression of star-height 1

Is there a regular expression of star-height 1 (i.e. without two nested Kleene stars) for the following language : $a^*(bb^*aa^*ba^*)^*$ ?
4
votes
2answers
241 views

Regular expressions and semi-linear sets

In proving Parikh's Theorem, my Theory of Computer Science textbook defines a linear set as: $u_0 + \langle u_1, \dots, u_m \rangle = \{u_0 + a_1u_1 + \dots + a_mu_m \mid a_1, \dots, a_m \in \mathbb{...
7
votes
2answers
1k views

Is the complement of { ww | … } context-free?

Define the language $L$ as $L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}$. In other words, $L$ contains the words that cannot be expressed as some word repeated twice. Is $L$ context-free or not? I'...
0
votes
0answers
28 views

How to see if P is decidable semi-decidable, undecidable?

I've been trying to figure out a practice exam question, about if a given $P$. $P$ is the characteristics of recursive enumerable set given as: $$P(A) = \begin{cases} ⊤ &if &|A| ≤ 100 \\ ...
5
votes
2answers
280 views

Does there exist context-free grammar with words of length n^2 or n^3?

Does there exist context-free grammar with words of length $n^2$ or $n^3$? I can't see any, we can produce all grammar with words of length $n$ ($S \to Se$), but then it seems to be impossible to ...
-3
votes
0answers
22 views

Bootcamp or self-teach? [closed]

Who out there is experienced a little bit with both and might be able to provide an answer here? I'm finding it very difficult to self-motivate at home, push through the walls, and even though it's a ...
-3
votes
1answer
45 views

L ={a^n.b^n | n>=0} , what is difference between L^2 and L.L?

which option is correct? please explain why other are wrong if any one is correct
5
votes
1answer
66 views

CFG Equivalent of regular expressions

So I was wondering something about the Chomsky hierarchy. DFAs (and NFAs) accept regular languages, while NPDAs accept context-free languages. Right-regular or left-regular grammars produce regular ...
-3
votes
0answers
7 views

its about how to uninstall bluestrack app player [closed]

any one can help me for how to remove bluestacks app player on my pc i get some idea below but it is totally dont work and get some error go cmd WMIC PRODUCT GAT NAME AFTER PRODUCT WHERE NAME="BLUE ...
0
votes
2answers
76 views

Is intersection of regular language and context free language is “always” context free language

I have read that intersection of regular language and context-free language is always context-free. Most of the places an standard example has been used to prove this, e.g., \begin{align*} L_1 &= ...
-1
votes
0answers
23 views

Intersection of two lanauages [on hold]

I'm preparing for my exam solving exercises from old exams. I'm not sure if my solutions are correct. Could you check following examples? 1) There is given $G_1=\{S_1 \rightarrow abS_1b,\ S_2 \...
-1
votes
2answers
79 views

Concatenation of $a^p$ and $a^m$ where $p$ and $m$ are primes, is irregular?

I believe that the concatenation $a^pa^m$ where $p$ and $m$ are primes is not regular, since I can show that $a^p$ is not regular using the pumping lemma, therefore there is no NFA for the 1st part, ...
61
votes
4answers
69k views

How to convert finite automata to regular expressions?

Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms, e.g. Thompson's algorithm. The other direction seems to be more tedious, though, and ...
0
votes
2answers
71 views

How to prove that a language $A$ is decidable?

How to prove: A language $A$ is decidable $\Leftrightarrow$ if there is a turing machine which lists $A$ in a word length alphabetically ordering. Word length alphabetically means a sorting first ...
-4
votes
0answers
37 views

Are the given languages semi - decidable?

I found this exercise in a pdf. Im not sure how to solve that exercise. I would be glad about if someone could help me, thanks. Are the given languages semi-decidable? a) $\left\{<M> \mid M is ...
2
votes
2answers
44 views

Is the punctuation part of the alphabet?

Given a language $L \subseteq \Sigma^*$, (it could be Italian, English, C++ or anything else), should we consider the punctuation (".", ";", "->") as a part of the alphabet $\Sigma$ upon the ...
3
votes
1answer
58 views

How to Trace Path in Proof that Regular Languages are Closed Under Reversal

I'm self studying automata theory and I need help with proving that regular languages are closed under reversal. I have a basic proof, but am unsure about last statement in my proof. Is this ...
-1
votes
1answer
44 views

What do we mean when we say an edge (u,v) connects some component to other component in forest G = (V,A)

Let H = (V,E) be a connected, undirected graph. Let A be a subset of E. Let C = (W , F) be a connected component (tree) in the forest G = (V,A). Let (u,v) be an edge connecting C to some other ...
-1
votes
1answer
36 views

Languages reducible to and from context-free

Let $L'$ be a context-free language. If $L \leq_M L' \leq_M L''$, where $\leq_M$ denotes mapping reducibility (aka many-one reducibility), what can we know about $L$ and $L''$? I think they're both ...
0
votes
0answers
25 views

Deriving properties of a language based on reductions [duplicate]

Assume there are three languages: $L_1$, which is the language of the Post correspondence problem (PCP), $L_2$, and $L_3$, which is the complement of the diagonal language. What can be said about $...
0
votes
0answers
13 views

Deriving properties of a language based on surrounding reductions

Assume there are three languages: $L_1$, which is the language of the Post correspondence problem (PCP), $L_2$, and $L_3$, which is the complement of the diagonal language. What can be said about $...
-2
votes
1answer
3k views

Regular expression for all strings with at least two 0s over alphabet {0,1}

My answer : (0+1)* 0 (0+1)* 0 (0+1)* Why is this incorrect? Can somebody explain to me what the correct answer is and why?
8
votes
2answers
180 views

Method for measuring the 'similarity' between FSA grammars?

I'm working with a pattern matching algorithm that generates an acyclic finite state automaton that accepts a given text string and all its substrings. The FSA algorithm is being run on a symbolic ...
0
votes
0answers
10 views

Struggling with Pumping Lemma application [duplicate]

I have studied Pumping Lemma carefully and have solved many exercises about it but I can't get an idea on how to solve this one: can anyone help me? Let L = { w#x | x is a substring of w }. Prove ...
1
vote
1answer
50 views

Why DCFL is not closed under kleene star?

I have read somewhere that DCFL is not closed under kleene star. but I haven't found any example
0
votes
1answer
42 views

Prove using pumping free lemma for context-free languages

One of the exercises I tried to make I failed miserably. The question was as follows: Show that the language $L = \{ w \,|\, n_a(w) \cdot n_b(w) = n_c(w) \}$ is not context-free. (with $n_a(w)$ ...
7
votes
3answers
1k views

Will $L = \{a^* b^*\}$ be classified as a regular language?

Will $L = \{a^* b^*\}$ be classified as a regular language? I am confused because I know that $L = \{a^n b^n\}$ is not regular. What difference does the kleene star make?
2
votes
1answer
75 views

Show that language generated by grammar is regular

We have grammar with nonterminals $ X_1,...X_n$ terminals $V_t$ and rewriting rules of form: $X_i \rightarrow a \in V_t $ $X_i \rightarrow X_jX_k, \ i \ge j , \ i > k $ How can I show that ...
11
votes
2answers
660 views

Why are regular expressions defined with union, concatenation and star operations?

A regular expresssion is defined recursively as $a$ for some $a \in \Sigma$ is a regular expression, $\varepsilon$ is a regular expression, $\emptyset$ is a regular expression, $(R_1 \cup R_2)$ ...
-5
votes
0answers
24 views

inclusion relation or equality of languages

Draw a bull's eye diagram that shows inclusion relation or equality between the following sets-Give an example in each case:  The set of regular expressions REX  The set of all regular languages ...
1
vote
1answer
44 views

Of which Chomsky-type is the language $L = \{a^jb^ic^{2i} | i,j \in \mathbb{N}^0\}$?

At first I thought the language would be context sensitive because it seems that it can be shown with the pumping lemma for regular languages, that it's not a regular language and analogously with the ...
14
votes
1answer
242 views

The number of different regular languages

Given an alphabet $\Sigma = \{ a,b \}$, how many different regular languages are there that can be accepted by an $n$-state non-deterministic finite automaton? As an example, let us consider $n=3$. ...
2
votes
1answer
33 views

How to use the Pumping Lemma to prove that a restricted subset of 0*1*2*3*, where there are as many 3's as 0's and 1's, is not a CFL?

Use the pumping lemma for context-free languages to show that the following language is not context-free: $ L = \{0^i 1^j 2^i 3^k \mid k=i+j \} $ So I have started like this: Let us assume that $ ...
-4
votes
1answer
71 views

Order classic notions of computability by power

I need some help with a question. I'm currently studying for an exam and I could therefore use some help with this following question: Order the following formalisms (but one) according to their ...
2
votes
1answer
32 views

Prove that language of possible stack content is regular

So, here's the problem: Suppose that $A=(Q,\Sigma,\Gamma,\delta,s,\bot, F)$ is a PDA, let $$L = \{ \gamma \in \Gamma^* \hspace{5pt}|\hspace{5pt} \exists_{x,y\in \Sigma^*} \exists_{q\in Q}: (s,x,\bot)...
2
votes
3answers
53 views

Is there a standard (common) notation for the following operation on binary strings?

Typically, we use the notation $S = \{0, 1\}^n$ to denote the set of all $n$-bit strings. Suppose that I wanted to extract a subset of the strings where certain bits have some fixed values. For ...
0
votes
0answers
6 views

OCL constraints are used to validate/verify instances of meta models. Which (v/v) is true?

I have a meta model of which valid instances are defined by OCL invariants. I'm not sure whether to say that I am validating or verifying instances of that model when I check whether they conform to ...
0
votes
1answer
39 views

The Chomsky–Schützenberger representation theorem

I've been trying to proof The Chomsky–Schützenberger, but I stuck on creating regular language from that theorem. I mean reagular language, which is intersected with Duck language. Could anyone give ...
1
vote
1answer
77 views

Can every context free grammar be transformed into equivalent grammar of this form?

Show, that every context free grammar can be transformed into equivalent context free grammar ( with possible loss of $\lambda $ ) where $a \in V_t$ and $A,B,C \in V_n $ with rewriting rules of ...
3
votes
0answers
54 views

Context free grammar as minimal solution of a system of equations

It is a well-known fact that language generated by a context-free grammar is the minimal solution of a particular system of equations, for example: $$\begin{align*} X &=\{{\epsilon}\} \cup Y\\ X ...
6
votes
1answer
3k views

Are all languages in P?

Are all languages in $\mathbf{P}$? Note: The definitions of all the symbols and functions here follow the document [1]. The following is my attempt to answer the question. Assume that we design a ...
13
votes
1answer
328 views

Is language equality for linear context-free grammars decidable?

Let's consider two context-free grammars $G_1$ and $G_2$ and ask the following question: Is $L(G_1) = L(G_2)$, that is, are the two grammars equivalent? In general, this problem is undecidable. ...
3
votes
1answer
38 views

How to recursively infer a word/string from a context-free grammar?

Give the recursive inference of the word $abcddd$ from the Context-free Grammar: $A\rightarrow aAd\mid B$ $B\rightarrow bBd\mid C$ $C\rightarrow cC\mid cD$ $D\rightarrow Dd\mid ϵ$ This is ...
4
votes
1answer
55 views

How to use Parikh's Theorem to show language is not context free

Parikh's Theorem is quite complicated, I understand intuition of that theorem but I don't see how to use that to prove that language is not context free. I kindly ask you to show me how to do, ...
0
votes
0answers
35 views

Pumping Lemma to prove that L is not context free

I have the language and I want to prove that is not context-free. So I started like this: is variable. Choose w = Case 1: vxy has no c. Choose i = 2 has more a than c or more b than c. Case 2: ...
0
votes
1answer
65 views

How to prove {a^(n^2) | n>0} is not context-free?

So I have a language: $$ L = \{a^{n^2} \mid n > 0\} $$ I need to prove that this language isn't context-free using the pumping lemma. I have a vague thought process as to how to do the proof but I'...
-3
votes
1answer
62 views

Is every countably infinite language recursive?

We'll say the alphabet for the languages is finite, say {0,1}.
2
votes
1answer
93 views

How to use a CFG to restrict a subset of a*b*c*d* so that there are at most as many a's and b's as d's?

Give Context-free Grammar for the language $\{a^i b^j c^k d^h \mid i,j,h \ge 0, k>0, i+j \le h\}$ This is a training exercise, for which we don't get any answers, in a course I'm taking. I have ...