New answers tagged

0

Try writing a few words that are contained (and not) in your language. See if you can discern some structure that helps answering your question. Hint: CS teachers are a devious, sadistic bunch. This might be a trick question...


0

I suggest you try some special cases. First, can you handle the special case where we force $k=2$? If not, work out how to solve that first, before handling the full problem. Next, try to handle the case where $k=3$. I recommend using the techniques in How to prove that a language is context-free? (specifically, look at the closure properties). Once you ...


0

You already have part of the answer for (a), but there's a bit more. For example, if $L_1 = \{a\}$ (and $\Sigma$ isn't just $a$) we certainly don't have $L_1\Sigma^* = \Sigma^*$. Can you come up with an extension? I knew you could.


2

This is one of those trap questions where $L_2$ can actually be written in a different way that makes it obvious that it is a regular language. See if you can figure out what $L_2$ is "really doing", and the answer will become obvious. Solution:


1

This proof uses both construction and knowledge of closure properties of regular languages. First, we know that regularity of languages is closed under the reversal operation, see proof of Thm. 4.2 here. We can then define an operation named chop such that: $$ \text{chop}(L)=\{w|aw \in L\}, \text{ where } a \in \Sigma, $$ We can construct an NFA for ...


3

Wikipedia says that taking the complement "can cause a double exponentially blow-up of its length" and cites the following paper: Succinctness of the Complement and Intersection of Regular Expressions. Wouter Gelade and Frank Neven. STAC 2008. In particular, they give a concrete language that triggers the doubly exponential blowup. See Theorem 4.1 in ...


0

$\{a,b\}$ is set notation. The alphabet of a language is the set of all possible symbol used in the language. You can substitute the typical $\Sigma$ for the full set every time. $\Sigma^*$ (where $^*$ is the kleene star) is the set of all possible strings you can make with that alphabet. That includes strings that happen to not use a certain character. ...


13

The DFA performs a single state transition on each read input symbol, reads each symbol of the input exactly once, and halts when the input string is exhausted. In order for an infinite loop of state transitions to happen, the input string has to be infinite. DFAs are usually defined for finite inputs only, as the automaton's output is defined by what state ...


1

The example is part of the construction to obtain a finite automaton for each regular expression. This construction is known as Thompson's construction and works recursively. Given automata $A(e_1)$ and $A(e_2)$ for expressions $e_1$ and $e_2$, instructions are given to build new automata for the expressions $e_1 + e_2$, $e_1\cdot e_2$ and $e_1^*$. These new ...


0

You are right in saying that those $\epsilon$-transition are useless. For the regular expression $ab$, a DFA with just three states (the initial state, an intermediate state, and a final state) and two transitions would suffice. A similar reasoning applies to the second NFA, where $4$ states are enough. I don't have the book to check, but maybe those are ...


3

As mentioned in the comments, you’ll need 8 states exactly. I like to label my states with semantic meanings, so in this case I’ll use a 3-digit number where each digit represents the number of as, bs, or cs we’ve seen ($\mod 2$). Then we have all the states from $000$ to $111$ in binary. You already know that $000$ is the start state and $010$ is the ...


27

A deterministic finite automaton can only go to infinite loop if the input string is infinite. For finite inputs, the automaton stops when the input string ends. For infinite inputs, for example the automaton for regex 0*1 will loop infinitely if the input string is an infinite sequence of 0.


0

The sticking point is in the first statement: CFL is not closed under intersection. That means, if we have L1,L2 of CFL then L1 intersection L2 is not a CFL This is not what non-closure means. What it actually means is that the intersection of two languages from a given set may not be in the given set, so in this case "CFL is not closed ...


2

Every CFL language can be describes as a PDA. Every regular language can be described as a DFA. The orthogonal product of a DFA and PDA can be defined as follows: The new states of the automaton are all $(q_{PDA}, q_{DFA})$. That start state is $(s_{PDA}, s_{DFA})$ and the final states are all $(f_{PDA}, f_{DFA})$ where $f_{PDA}\in F_{PDA}$ and $f_{DFA} \...


1

The first language can be described as the set of words on the alphabet $\{a,b\}$ with an even number of $b$'s. The second one is not the language of words on the alphabet $\{a,b,c\}$ with an equal number of $b$'s and $c$'s (this condition would define a non-regular language). You could use greybeard's description or say: the language contains the empty ...


0

Based on the book, Introduction to Languages and the Theory of Computation , they are interchangeable terms. ... These are examples of a type of language acceptor called a finite automaton (FA), or finite-state machine.


0

Use closure properties. Define homomorphisms $h_1$ and $h_2$ as follows: $\begin{align*} h_1(x) &= \begin{cases} x & x \in \Sigma \\ \sigma & x = A \text{ (a new symbol)} \end{cases} \\ h_2(x) &= \begin{cases} x & x \in \Sigma \\ \tau & x = A \end{cases} \...


2

There are many ways to perform this enumeration. Note first that you can count the number of cases in half by postulating that $Q = \{q_0,q_1\}$, that is, fixing which among the two states is initial; the choice doesn't matter due to symmetry. Now you are left with 16 possibilities. At this point there are many ways to cut the search space even further. Here ...


Top 50 recent answers are included