Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

-2
votes
0answers
11 views

Practical Applications of theory of computation [on hold]

Apart from compiler design, what are the various fields in which theory of computation is used. As this subject is often called mother of Computer Science
1
vote
1answer
45 views

How do I find a regular expression for a particular language?

I have a language, and I want to find a regular expression for the language. How do I do that? Is there a step-by-step, systematic procedure for that? Pretend I am just learning this topic; what ...
0
votes
1answer
38 views

Regular expression - every b preceded and followed by an even number of a's

I'm trying to write a regular expression over the alphabet $\{a, b\}$ for the language in which every $b$ is preceded and followed by an even number of $a$'s. I think the regular expression should ...
2
votes
1answer
38 views

Have non-regular language classes of infinite words been studied?

For regular languages we have $\omega$-regular languages which extend them to infinite words. Are there such extensions for CFG's, CSG's and recursively enumerable languages?
-3
votes
0answers
21 views

Why is this regular expression equivalent to this automaton? [duplicate]

Given this automaton $A$: Why is $\qquad L(A) = L((11^*0+0)(0 + 1)^*0^*1^*)$? Please explain in a descriptive way step by step.
6
votes
1answer
141 views

What is the relationship between problems and languages?

I want to ask exactly what is the relationship between problems and languages. We know that the set of all languages uncountable. Is the set of problems also uncountable? Can every problem be ...
0
votes
1answer
42 views

Decidable language: set of context-free langauges containing 1 string

ONE = {(G) : G is a CFG such that L(G) contains exactly one string} . I know to prove this is decidable I need to create a DTM that would recognize it and HALT on all input. I am struggling at ...
4
votes
1answer
88 views

What's wrong with my pumping lemma proof?

The language $L = \{0^{2n} \space |\space n \ge 0 \}$ is obviously regular – for example, it matches the regular expression $(00)^*$. But the following pumping lemma argument seems to show it's ...
-4
votes
1answer
29 views

What is the relation between a regular language, $L$, and $\Sigma^*$? [closed]

Let's say I have $\Sigma = \{0\}$. Can a language $L$ be as large as $\Sigma^*$? So $L = \Sigma^*$. Can a language $L$ be as small as just $\{0\}$? A subset of $\Sigma^*$. Can multiple languages, ...
0
votes
2answers
89 views

Is $\epsilon$ always contained in $\Sigma^*$? [closed]

Please correct me on any terminology. For some reason I'm a bit confused. $\Sigma = \{\epsilon, 0, 1\}$ This means my alphabet, $\Sigma$, contains three symbols ($\epsilon, 0, 1$). $\Sigma^*$ is ...
8
votes
2answers
329 views

Kleene star operation on the empty language

In my text book it is mentioned that: $\emptyset^*=\{\epsilon\}$ where $\emptyset$ is an empty language. However, we know that $L \cdot \emptyset = \emptyset$, where $L$ is any Language. I am not ...
11
votes
2answers
153 views

When is the concatenation of two regular languages unambiguous?

Given languages $A$ and $B$, let's say that their concatenation $AB$ is unambiguous if for all words $w \in AB$, there is exactly one decomposition $w = ab$ with $a \in A$ and $b \in B$, and ambiguous ...
4
votes
2answers
79 views

From context-free to context-sensitive

I have a context-free language $L(G)$. I'm reading in a book that $L(G') = L(G) - \{{\epsilon}\}$ is context-sensitive but I cannot find a proof or confirmation of this fact; moreover, in other texts ...
2
votes
0answers
28 views

Z into Isabelle [migrated]

I am trying to input and prove Z specifications in Isabelle. Say I have a vending machine specification written in the LaTeX format: ...
0
votes
1answer
65 views

Model paths by regular languages [closed]

I want use DFA to describe a sequence of movements in a 2D-space (language will be the path accepted by automaton in a particular case). That is a typical modeling problem: how can I encode a ...
6
votes
4answers
60 views

Minimal size of a context-free grammar which defines $L_n=\{a^k\mid 1\le k\le n\}$

I am looking for the minimal size of a context-free grammar which defines the finite language $$L_n=\{a^k\mid 1\le k\le n\}.$$ The size of a grammar is defined as the total length of all right-hand ...
3
votes
1answer
38 views

Formal languages: constructing * for a linear set

Right now, I'm working on a computer verified proof in Agda, showing that the Parikh images of regular languages are semi-linear (i.e. a limited form of Parikh's Theorem). Right now, I'm trying to ...
1
vote
1answer
41 views

Showing that the pumping lemma cannot prove that some language is not regular

I have this language $ L = a^* \cup \left \{ a^mb^n|m>n\geq 0 \right \}^* $ I have to prove that this language is not regular but still satisfies the pumping lemma for regular languages (Since the ...
0
votes
0answers
21 views

Rules language / DSL expressivity measure

Languages to express domain rules are quite diverse from very simple and inexpressive to Turing-complete programming languages. If we consider developing some DSL (domain-specific language), is there ...
0
votes
1answer
42 views

Prove language is regular [duplicate]

let's have these two languages in the alphabet $\{a,b,c\}$: $L_1 = \{ w \mid w \text{ is a palindrome and $|w| < 200$}\}$ $L_2 = \{ w \mid w \text{ is a suffix of $u$ and $|u|$ is a prime number ...
0
votes
1answer
56 views

Regular Expression from Context Free Grammar [duplicate]

The purpose of this exercise is to write a program that recognize all the words derived from this grammar. The time complexity of this program must be O(n) hence i must be able to derive a regular ...
0
votes
1answer
28 views

prove language is Context-free and not regular [duplicate]

I have to prove that $\left \{ a, b \right \}^{\ast} - \left \{ a^ib^i | i\geq 0 \right \}$ is a context-free language and it's not regular. So far I've got that this language is not regular because ...
3
votes
1answer
55 views

Symmetric Difference of Turing Recognizable and Finite Languages

Let A be a Turing Recognizable Language and B a finite Language. I want to prove that their symmetric difference is Turing Recognizable. My reasoning: B is finite, therefore the finite number of ...
0
votes
2answers
32 views

Push down automata what to do when there is no suitable transition

This is a question that has emerged from a recent quiz I have taken. In short Consider the following transitions on a push down automaton. Assume the starting state is q. Which one of the ...
-2
votes
1answer
53 views

How to convert this type of languages to Context Free grammar?

As I've already asked my Question about the solving Context Free Grammar $L = \{a^n b^m c^p \mid n = m + p + 2\}$ Can this language be defined by a Context Free Grammar? Now i have just changed ...
-1
votes
1answer
144 views

Does every language that fulfills the regular Pumping conditions also fulfill the context-free ones?

Let L be a language that fulfills the properties implies by the Pumping lemma for regular languages. Does L necessarily fulfill the corresponding properties of the Pumping lemma for context-free ...
0
votes
0answers
10 views

Construction of NPDA with inequality check [duplicate]

I'm currently struggling to construct a nondeterministic PDA with an amount of states in $O(n)$ that accepts the following language: $L = \{wcx \, | \, w,x \in \{a,b\}^n \land w \not= x\}$ with c ...
2
votes
2answers
142 views

Can this language be defined by a Context Free Grammer?

I was solving one of my practice questions, defining a language with Context Free Grammar Productions , but I am stuck on one question , Here are my attempt: Question: $L = \{a^n b^m c^p \mid n = m + ...
0
votes
1answer
33 views

Proving that a set of grammars for a given finite language is decidable [duplicate]

Let the language $$L = \left\{ \langle G \rangle \ |\ L(G) = \{1,\ldots , 1000\}, \text{ G is a CFG }\right\}$$ Prove that $L \in R$. Well, I think that for a start we need to check whether or ...
4
votes
4answers
137 views

Does Thompson's algorithm produce optimal NFAs?

I'm using Thompson's algorithm to convert from a regular expression to a NFA. Is Thompson's algorithm guaranteed to always output a minimal NFA, i.e., a NFA with the smallest possible number of ...
1
vote
0answers
61 views

Are DCFLs closed under concatenation with a regular language?

I have found various opinions saying they are (a link to one is given in D.W.'s comment). However, a proof that DCFLs themselves are not closed under concatenation found here on StackExchange seems to ...
5
votes
2answers
263 views

Is an inverse homomorphism always a homomorphism?

Given a homomorphism $h: \Sigma \rightarrow \Delta^*$ such that e.g. $\forall a \in \Sigma: h(a) = \delta$, where $\delta \in \Delta$ (i.e. all symbols from the alphabet $\Sigma$ have the same image ...
0
votes
2answers
62 views

How does this Turing machine accept $a^n b^n$?

I'm reading this tutorial from the University of Illinois about Turing Machines, and I don't understand something. They give a pseudocode algorithm for an machine that accepts strings from the ...
-4
votes
1answer
30 views

Is $Σ^∗$ finite? [closed]

Suppose $Σ=\{0,1\}$; then $Σ^*$ is all combinations of $Σ$. So my question: is $Σ^*$ finite?
0
votes
0answers
58 views

The pumping lemma - Proving that this language is NOT context free

I would like to find out if this language is context free or not: $\qquad L=\{a^{i}b^{j}c^{k} \mid i<j,i+2j+3<k\}$. I've tried to apply the pumping lemma taking out $w=a^n b^{n+1}c^{3n+6}$ ...
0
votes
3answers
51 views

Construct Turing Machine which accepts the language $ww$

I try to construct a TM that accepts the language $\{ ww \mid w \in \{a,b\}^* \}$. Between the words $w$ is no delimeter, so I don't know, how my TM can know where the first $w$ ends and the second ...
0
votes
1answer
50 views

Context free grammar for this language [duplicate]

Is this language Context Free? $L=\{a^{n+3} b^{2m} \mid n \neq m \}$ I think that I could split the languages into $L_1$ and $L_2$ with the conditions $n<m$ and $n>m$, provide 2 CF grammars ...
0
votes
1answer
67 views

Using the pumping lemma to prove that a language is context-free [duplicate]

I am new to automata theory. Could you give me a little hand with the correct use of the pumping lemma? I understand now how to proof a language is not context-free, but how do I use the pumping ...
0
votes
0answers
20 views

Prove this language is not CFL [duplicate]

I have this language: $L = \{a^{n+2} b^m a^{2n} b^{3n}\mid n,m >=0 \}$ and I am trying to prove that it is not CFL. I assumed that my word is $a^{p+2} b^m a^{2p} b^{3p}$ (where $p$ is the pumpung ...
0
votes
1answer
38 views

How can I prove this language is not CFL? [duplicate]

I have a question to find out that $L = \{a^m b^n\mid n>0, m - is prime \}$ is CFL or not. I know that it is not a CFL. But I don't know how to prove that. I know how to prove that $L = \{a^m\mid m ...
0
votes
0answers
106 views

What is the limit for Turing machines with 2 states and 3 symbols that halt?

I read here that a proof has been offered that a Turing Machine with 2 states and 3 symbols can be universal (in that it is capable of arbitrary finite computations). Even if this proof is accepted, ...
0
votes
1answer
46 views

How to prove that the language { ww | w ∈ {a,b}* } is / isn't context free? [duplicate]

Is the language { ww | w ∈ {a,b}* } context free? I have tried to create a pushdown automaton but I didn't find any solution. I think you need a queue and not a stack. Is there a way to prove this ...
0
votes
1answer
78 views

Is the language $L=\{a^{2^{n}} \mid$ n is a natural number$\} $ context free?

I have to determine, and prove, whether the language $L=\{a^{2^{n}} \mid$ n is a natural number$\}$ is context free or not (if it is by a grammar and not by the pumping lemma). I tried to construct ...
1
vote
1answer
44 views

Irregularity of L = {a^i b^(j+3)| i!=j }

I have a question to find out that $L = \{a^i b^{j+3}\mid i\ne j \}$ is regular or not. I know that it is not regular. I tried with pumping lemma but I am finding just a specific number of $v$'s in $u ...
1
vote
0answers
50 views

How to convert CFG with Kleene Star, Kleene Plus, and Question Mark to Chomsky Normal Form?

I am fairly new to formal language theory but understand how to convert simple CFGs into both Chomsky normal form and Greibach normal form. However, I have not seen any examples of how to do that when ...
-2
votes
1answer
33 views

Formal Languages and Automata Theory [duplicate]

How can I show that $L = \{a^m b^n \mid (m > n \text{ or } m < n) \text{ and } m, n ≥ 1\}$ is not a regular language.
-2
votes
1answer
24 views

Union of two languages [closed]

If I have these languages: $$\begin{align*} S&=\{a,b,c,d,e,f,g,h\}\\ A&=\{b,g\}\\ B&=\{a,b,c,d,f,h\}\\ C&=\{a,c,g\}\,, \end{align*}$$ Writing $X'$ for the complement of a set $X$, ...
0
votes
1answer
29 views

How to read this inductive language definition?

A language $L$ is defined recursively according to the following rules: $λ ∈ L$ If $w ∈ L$, then $bw ∈ L$ and $waa ∈ L$ I am not sure if strings from this language should mix from this definition. ...
6
votes
1answer
52 views

Smallest class of automata model whose corresponding language class contains CFL and is closed against (dis)allowing nondeterminism in the model

From a comment, an interesting question popped up. The class of CFLs (the languages recognized by PDAs) are obviously not closed under nondeterminism - what I mean by this is that deterministic PDAs ...
8
votes
0answers
66 views

Machines for context-free languages which gain no extra power from nondeterminism

When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines. For the ...