Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

learn more… | top users | synonyms

0
votes
1answer
37 views

What does q-prime ($q'$) actually mean?

I'm learning about finite automata right now, and struggling with a bit of the math notation. In the explanation here: http://math.stackexchange.com/a/563875/125649, the user explains that the ...
0
votes
1answer
61 views

Prove or disprove that the language $L_1 = \{a^nb^m \mid n < m \}$ is regular

I have possible strategy for a proof that it is not regular. I am wondering if it is valid. Step 1: Prove that the language $L_2 = \{a^nb^n\}$ is not regular (for example with the Pumping Lemma). ...
0
votes
2answers
23 views

Proof that suffix of $ab$ needs at least 3 states in NFA

I need to prove that for an NFA that accepts all languages $L(M)=\{w \in \{a,b\}^* \mid wab \}$ with a suffix of $ab$ needs at least 3 states. The smallest automata would look like this: $\to(s) \to ...
0
votes
1answer
27 views

Create a general NFA for $M_n$

I need to create a general NFA $M_n$ where $n \in \mathbb{N_0}$ with the following language defined: $$L(M_n) = \left\{ w \in \{0,1\}^* \big | x1y \textit{ for } x \in \{0,1\}^* \textit{ and } y \in ...
0
votes
2answers
68 views

Turing machine true/false questions

There is a non-regular language that is recognized by a Turing Machine. I believe the answer to this is true, because Turing machines can "count" computations and ...
0
votes
1answer
47 views

Proof by pumping lemma

Let's say that we have to prove that $L = \{ww^Rv |w,v\in \Sigma^*\}$ is irregular. I would take a string such that $w = baba^m$ and $w^R=a^mbab$ and $v = a$ and then I would pump divide $w$ into ...
0
votes
2answers
35 views

Determining a language with a Turing Machine

How can I build a Turing Machine that determines the following language? $$L_{E - DFA} = \{\langle A \rangle | \text{$A$ is a $DFA$ and $L(A) = \varnothing$}\}$$ Thanks alot
0
votes
1answer
77 views

Why isn't this a sufficient proof?

So basically, we have a question that asks us to prove that given a particular Deterministic finite automaton (DFA), there is a symbol for which we can get to a state $q$ from a state $p$ given a ...
0
votes
3answers
25 views

If $s \geq 3$, $3$ divides $s$, and $t = s/3$, then $t+1 < s$.

I am using the pumping lemma to prove a language is not regular, and would like to assert what I have stated in the title of the question to complete my proof. That is, if $s \geq 3$, $3$ divides $s$, ...
0
votes
1answer
118 views

Prove that a PDA with accept states accepts all context-free languages

Or in other words that $\forall L: L \in DCFL => L \in CFL$. First of all, does this statement even require a proof? My idea was to let L be an arbitrary language, such that $L \in DCFL$, this ...
0
votes
1answer
18 views

proving regular language

let $L$ be a language over the alphabet $\{a,b\}$ that maintains that for each $w \in L$ ,the difference in absolute between the number of apearences of the letter $a$ and the number of apearences ...
0
votes
1answer
37 views

Question about second condition of pumping lemma

I don't think that I fully understand how to use the pumping lemma to prove that a given language is not regular. I'm reading Sipser and according to him the definition of the pumping lemma is: "If A ...
0
votes
1answer
85 views

Is $\epsilon$ in every alphabet?

Given a $\Sigma$ an alphabet, is $\epsilon$ in it logically? For example, if I have a function $ f : \Sigma \to \Sigma $, can I define it for example $ f(\sigma) = \epsilon$? even if my alphabet is ...
0
votes
1answer
48 views

Showing a grammar to be ambiguous

I'm learning about grammar ambiguity and trying to show the following grammar is ambiguous: $S \rightarrow ScS | SdS | A$ $A \rightarrow a | b$ I used 2 different left-derivations to get the same ...
0
votes
1answer
83 views

Grammar into Chomsky Normal Form

Convert the following grammar into Chomsky Normal Form (CNF): S → aS | aAA | bB A → aA | λ B → bB | aaB I think this looks ok, but not sure. Maybe someone can point out where I go wrong: ...
0
votes
1answer
54 views

Construct an automaton by using sliding window method

Given alphabet $\Gamma = \{0,1\}$, let $L = \{\omega : All\ words\ ending\ 010\}$ be a language. Find an automaton. I have to find an automaton using sliding window method.. First I need some ...
0
votes
1answer
209 views

Show that a language is not regular using Myhill-Nerode Theorem

I'd like to show that the language below is not regular using Myhill-Nerode Theorem. How can I do that? Let Σ = {0, 1}. Let L = {ww|w ∈ Σ*} I am not sure where ...
0
votes
2answers
66 views

Constructing regular grammar

I'm trying to make a regular grammar for this language: $$ L = \{ a^ncb^m(cc)^p : n\ge 1, m\le 1, p\ge 0\} $$ Where the alphabet is $ \Sigma = \{a,b,c\}$ It seemed like right-linear. This may be ...
0
votes
2answers
52 views

context free grammar design

Design a context free grammar and PDA for the following language. $$\Sigma = \{0,1\},\qquad L = \left\{uv \mid u \in \sum^{*} \;v\in \sum^{*}1\sum^{*} \text{ with }|u| \geq |v| \right\}$$ I'm not ...
0
votes
2answers
56 views

$2^E$ where $E$ is a set

I'm studing the definition of automaton $G=(X, E, f, \Gamma, x_o, X_m)$ where $X$ is the set of states and $E$ is the set of events. My sources report that $\Gamma:X \rightarrow 2^E$ is the indicator ...
0
votes
1answer
48 views

Connection of closed subsets of $A^{\omega}$ and deterministic Büchi-Automata, Question from Book: Infinite Word by D. Perrin & J.-E. Pin

In the Book Infinite Words (homepage) it is proofed that: If $X \subseteq A^{\omega}$, then regarding the Cantor-Topology, the following is equivalent: (1) $X$ is closed (2) $X$ is recognized by a ...
0
votes
1answer
118 views

Proving what are the equivalence classes of the relation $R_{L}$

I tried writing a solution for a question that defined a language $L$ and asked to find the equivalence classes of the relation $R_{L}$ The TA wrote that "this is not what you should prove" (or "this ...
0
votes
1answer
52 views

Legal actions on a PDA and terminology

I am unsure about the following so I would like to verify if my statements are true: We can remove at most a single character ($Z\in\Gamma$) from the PDA (top ?) of the stack with one step of the ...
0
votes
1answer
47 views

Given two NFAs, is there a way to figure out if there exists a language that works for both of them?

Given two non-deterministic finite automaton, is there a way to determine if there exists a single language that satisfies them both?
0
votes
1answer
120 views

A question about the regular languages being closed under Boolean operation (how to generalize)

I know that if $L_{1},L_{2}$ are regular languages then so is $L_{1}\cap L_{2},L_{1}\cup L_{2}$ are regular languages, I also know that $L$ is regular $\implies L^{c}$ is regular . It is easy to ...
0
votes
1answer
83 views

How to prove that the language of a DFA is some $L$

Consider the following DFA: It is quite clear that the language of this FDA is all the words that don't have the word $aa$ as a subword. My question is: How can I formally prove that this is the ...
0
votes
3answers
214 views

Different version of pumping lemma and how to prove it

I have a question to solve but I am not even getting a direction to start or how to narrow down this problem. Please provide in your inputs. Consider the following version of pumping lemma. For any ...
0
votes
2answers
423 views

String matching automata preprocessing

I have an alphabet A = {a,b,c} and a pattern P = "abcaab". The task is to build a finite automaton of the transition function (delta) for {0,6} (the length of the pattern) and each element of the ...
0
votes
2answers
226 views

How can I prove that this language is regular?

Given a language $L$, define the language $K$ as the language $L$ where every second character is replaced with a $\#$. (Note: $\#$ is not part of the alphabet of $L$.) For example, if $L = \{ab, ...
0
votes
2answers
28 views

Is there a fast way to know whether a language is regular or not?

Or at least have an idea? Because I can't see whether a language is regular before I can disprove it by pumping lemma and it takes me like a hour to try to disprove.
0
votes
1answer
29 views

using pumping lemma to prove that a set is not regular

A={s11s|s $\epsilon$ {0}^*} so the strings 00011000 and 000001100000 are accepted of A but not 00100 or 001100000. Demon chooses k. ...
0
votes
1answer
56 views

How to convert this NFA to DFA?

http://www.cs.odu.edu/~toida/nerzic/390teched/regular/fa/figures/nfa-dfa1.jpg What are the steps for convert this NFA to DFA??
0
votes
1answer
55 views

Using the Pumping Lemma to prove a language is not regular.

I want to know if my proof is wrong and whether what I am doing works. $$\sigma = \{0, 1\}$$ $$A = \{0^n1^m \mid n < m\}$$ Claim: A is not regular. Proof: Assume A is regular. Let p be the ...
0
votes
1answer
24 views

Question about Notation in a Regular Language

I am a little confused about the following notation: $L' = \{xy|x\in L \ , y\in L^R\}$. I think this expression is not equivalent with palindrome but I am not entirely sure. For example, I think the ...
0
votes
1answer
57 views

find a regular expression and FA that each define L1 ∩ L2

from the following pairs I am trying to find a regular expression and FA that each define ...
0
votes
1answer
22 views

How can I show ithat a language is regular?

I have a very quick question about regular languages, I think $\{a^{2n}| n\geq 1\}$ is regular. I do know that pumping lemma can be used to show something that is not regular. I am wondering what ...
0
votes
1answer
27 views

Question About Pumping Lemma used on a FA

I am learning about pumping lemma and I am trying to solve a problem. I need to use pumping lemma to show that: the Language L(M) defined by the following machine is infinite. Here is the dfa: ...
0
votes
2answers
91 views

Show that, given regular expression $R$, we can decide whether $L(R)$ is prefix-free

Suppose language $L$ is called prefix-free if no member is a proper prefix of another. For instance, cat is a proper prefix of category and so $L = \{cat,category,ego,go,rye\}$ is not prefix free. ...
0
votes
1answer
40 views

Creating a Push Down Automaton from a Grammar

I have the following grammar, but I'm not sure what exactly it is that it does: $\qquad\begin{align} S &\to S \vee T \mid T \\ T &\to T \wedge F \mid F \\ F &\to p \mid \thicksim p ...
0
votes
2answers
324 views

Regular expression and DFA/NFA questions

If a language L is generated by a regular expression, then L is recognized by a DFA. I think this is true, because regular expressions describe regular languages, those of which are exactly ...
0
votes
1answer
20 views

Reversed Language of a Non Regular Language

Is the following saying true or false? In any case why? Thanks!
0
votes
1answer
73 views

Finding regular expressions

I'm given the DFA shown below and need to find regular expressions for the following languages: $L_{1,2}^0, L_{2,1}^6, L_{2,5}^4, L_{2,3}^5, L_{1,3}^5$. The language $L_{p,q}^r$ is defined as ...
0
votes
1answer
31 views

Help Specify possible definitions for this Boolean Function

My math is rusty, but I need some guidance here. Problem I wish to design a stochastic, boolean procedure $f(state)$, that picks a winner, $f(state_{win})\to 1$ or loser, $f(state_{loss})\to 0$. I ...
0
votes
2answers
111 views

What is the language generated by G and how to draw the finite state automaton that recognizes this language?

G = (V, T, S, P) V = (0, 1, A, B, S) T = {0, 1} S is start S -> 0A S -> 1A A -> 0B B -> 1A B -> 1 For the drawing, I am confused about the last ...
0
votes
1answer
128 views

unrestricted grammar and Turing machines

Let $G$ be an unrestricted grammar. Then the problem of determining whether or not $L(G) = ∅$ is undecidable. Let $M_1$ and $M_2$ be two arbitrary Turing machines. Show that the problem $L(M_1) ⊆ ...
0
votes
1answer
80 views

DFA with $k$ states, words of length $k$

Is this statement true? If we have a DFA with $k$ states, and if $L(M) = L$ is infinite, then there is a word of length at least $k$ and at most $2k-1$. Isn't this a trivial answer? Take the ...
0
votes
1answer
104 views

Converting NFA to DFA

Im trying to convert a NFA to DFA. This is the NFA and this is the DFA to which i converted Is this right? Also when converting if i write a state as [q0,q1] is this same as [q1,q0] edit: ...
0
votes
1answer
63 views

Proving Equivalence of DFA and NFA

Im trying to learn Equivalence of DFA and NFA.The problem is that in the below explanation Q' is given as the power set of Q.But this statement seems to be contradictory to the previous statement ...
0
votes
1answer
17 views

How is Finite Automation Linked to Lexical Analyser

I understand that Finite Automaton is a Mathematical model of a system with discrete number of input and outputs. Also the system has finite number of states.My question is how is this linked with ...
0
votes
1answer
68 views

Designing PDAs to Accept Languages

I want to design PDAs to accept the following two languages: $L_1 = \{a^ib^jc^k \mid i=j \text{ or } j=k\}$ $L_2 = $ The set of all strings with twice as many $0$s as $1$s. I am especially ...