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

learn more… | top users | synonyms

0
votes
1answer
40 views

Prove the following context-free language is generated by this grammar.

I would like to prove the context-free language $$ \mathcal{A} = \{ w\#x ~:~ w^R \text{ is a substring of $x$ for } w,x \in \{0,1\}^* \}, $$ has the context free grammar \begin{align*} ...
0
votes
1answer
36 views

Construct an automata for this language

Let $\mathcal{L}_1$ be the language over alphabet $\{0,1\}^*$. Define language $\mathcal{L}_2$, call even-$\mathcal{L}_1$, as: $$\mathcal{L}_2 = \{ w_2 w_4 \ldots w_{k} ~:~ w_1 w_2 w_3 w_4 \ldots ...
0
votes
1answer
20 views

Building a Deterministic Finite Automaton with the set {a}

Design a DFA for the set of strings in $\{a\}$* such that it's length is divisible by 3 or 5. The point that I am not understanding is, how many states do we need? Since we can't possibly represent ...
0
votes
2answers
26 views

Language of Grammar

Let $G = (V,T,S,P)$ be the phrase structure grammar with $V = \{0,1,A,S\}$, $T=\{0,1\}$, and a set of productions $P$ consisting of: $S \to 1S$ $S \to 00A$ $A \to 0A$ $A \to 0$ What is the ...
0
votes
1answer
27 views

Designing a Pushdown Automation to accept a language

Im a novice trying to understand the theory of computation.Im trtying to learn about PDA.I understand that it is a machine counterpart of CFG.Im basically referring to Introduction to Automata Theory ...
0
votes
1answer
32 views

Definition of “equivalence classes”

I am studying finite state automata and learning how to prove a machine uses the minimum number of states. I have come across the Myhill-Nerode theorem and one of the corollaries states the following ...
0
votes
1answer
37 views

For $\sum = \{ 0,1 \}$, $A$ has strings which contain a $1$ in their middle third, and a $B$ which contain two $1$'s in their middle third.

Language $A$ can also be represented as, $$A = \{ uvw \mid u,w \in \sum^*\text{ and, }v \in \sum^* 1 \sum^*\text{ and, }|u| = |w| \ge |v| \}$$ Language $B$ can also be represented as, $$B = \{ uvw ...
0
votes
1answer
31 views

Nondeterministic finite automaton understanding problem

It is probably a silly question but I have problem understanding it. Let's say I have to design a nondeterministic finite automaton that accepts the language consisting of words containing a string of ...
0
votes
1answer
47 views

Pushdown automaton design

I have to design a PDA that recognizes the language: $$L=\{w \mid \#(a,w) - 3\#(b,w) = 2\} $$ where $\#(a,w)$ means the number of letters $a$ in $w$ My idea is to count $a$'s and $b$'s. I have to ...
0
votes
1answer
28 views

Pumping lemma to prove that a language is not context free

We've got $L = 0^{x^{2}}$. So we let $w = 0^{p^{2}}$, and we know that we can split w into $w = u\cdot v\cdot w\cdot x\cdot y$ , according to the pumping lemma for CFGs. I'd like to know how to ...
0
votes
1answer
53 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
93 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
59 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 ...
0
votes
2answers
146 views

Input and output of a Turing machine

For some machine models of computation there is no question what their input and output is: it's just the contents of some specific "cells", e.g. on a "tape" isomorphic to $\mathbb{N}$. Consider for ...
0
votes
1answer
60 views

Use the power-set construction to find a deterministic automata

Given a nondeterministc automata N, how do you use the power-set construction to find a deterministic automata that recognizes L(N)? Here is my work so far: We can start in state 1, 2. If we get ...
0
votes
1answer
29 views

Soft question, Understanding NFAs and DFAs; Requirements for either.

I have a few quick questions about NFAs and DFAs. Is any automaton with epsilon transitions always a NFA? Is any automaton with two paths for the same symbol from a state always a NFA? Ex. Say state ...
0
votes
2answers
34 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
39 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
237 views

How to convert this NFA to DFA?

What are the steps for converting this NFA to a DFA??
0
votes
1answer
63 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
35 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
172 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
29 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
41 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
141 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
73 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
385 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
24 views

Reversed Language of a Non Regular Language

Is the following saying true or false? In any case why? Thanks!
0
votes
1answer
85 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
149 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
108 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
452 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
88 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
27 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
85 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 ...
0
votes
1answer
75 views

Prove/Disprove: $vwvw=vvww$ iff $\{v\}^*\{w\}^*=\{vw\}^*$

Let $\Sigma$ be an alphabet and $v,w\in \Sigma^*$. I'm trying to prove that: $$vwvw=vvww\quad\text{iff}\quad\{v\}^*\{w\}^*=\{vw\}^*.$$ I tried to do it by induction, with no success. Any help will ...
0
votes
1answer
39 views

Grammar derivation

Given these grammar productions: $$\begin{align*} &S\to A1B\\ &A\to 0A\mid\lambda\\ &B\to 0B\mid 1B\mid\lambda \end{align*}$$ And given string $w = 01101$ If I wanted to make a) ...
0
votes
1answer
38 views

S-grammar for this regular expression

Given this regular expression: $r = a a^* b + b^* c b$ I think this is the simple grammar, but I was getting a little lost with the productions: $S \rightarrow S_1 | S_2$ $S_1 \rightarrow a A b$ ...
0
votes
2answers
35 views

Regular Language Operation

I need to show that the given regular language is closed under the following operation. For example: AllSuffixes(L) = {v : uv in L for some u in (0+1)* } I do not ...
0
votes
2answers
82 views

Can someone explain this automaton?

I have a question about constructing an automaton for given language: $$L = \{000, 010, 100, 110\}$$ Solution for this was given below. Can anyone explain why this automaton accepts the language? This ...
0
votes
2answers
350 views

Is it true that any infinite subset of a non-regular unary language is non-regular?

My question is very similar to this: Is there a subset of a non regular language that is regular My claim is that because the subset is infinite, Myhill Nerode says that the language is not regular. ...
0
votes
2answers
131 views

Pumping Lemma to show a language is not regular

Let $\Sigma = \{a, b\}$. Use the Pumping Lemma to show that $\mathcal L = \{ a^pab^q: p < q \}$ is not regular. Not sure how to apply PL here, if someone can give some direction.
0
votes
1answer
216 views

Right-linear grammar from regular expression

I made a right-linear grammar that from this regular expression: The alphabet is: $Σ = \{a, b, c\} $ Regular expression: $r = cc^*(ba)^*bb$ My solution, it seems a little too short like I'm ...
0
votes
1answer
31 views

Language made by a regular expression

I created a language from this regular expression but I'm not sure about it, especially where I wanted to use the $w$ to express a sequence of terminals. The expression: $r = a a ^{*} (b + bb + bbb) ...
0
votes
2answers
501 views

Finite automata for any even number of a's followed by any even number of b's

I'm new to formal languages. I'm stuck with the following question. Any help is appreciated. Find finite automata for $$L = \{a^i b^j \mid i, j\text{ are even, }j\ge0\}$$ Thank you
0
votes
2answers
791 views

To design a Finite State machine

Design a FSM for a binary number in which the input is valid if no. of 0's divisible by 5 and no. of 1's divisible by 3
0
votes
1answer
162 views

Is this language regular?

Given $m,n∈Z$, A is a finite alphabet set ,and $L=\{(a^m,a^n)\}^*$ is subset of $A^*\times A^*$ . Is this language regular ? For example, is $L=\{(a^3,a^7)\}^*$ regular ? Here L is not the set ...
0
votes
2answers
224 views

Prove $L=\{ 1^n| n\hspace{2mm}\text{is a prime number} \}$ is not regular.

Prove $L=\{ 1^n| n\hspace{2mm}\text{is a prime number} \}$ is not regular. It seems to use one Lemma: Pumping Lemma.
0
votes
1answer
46 views

Given a DFA $\mathcal{M} = (S, \Sigma, q_0, \delta, F)$, is there an algorithm that finds the pumping length of $L(\mathcal{M}$)?

This question has been bugging me for a while, and I'm curious what such an algorithm would look like, if it exists. My guess is that it does exist, but I'm not sure how it would look.